用dfs枚举+剪枝

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int s1, d1, s2, d2;
int a[6][6];
bool visited[6][6];
int min_cost = 1<<30;
int now_cost = 0;
int state = 1;//状态
int cal_cost_and_state( int c, int d) {
	int cost = state * a[c][d];
	state = cost % 4 + 1;//更新状态
	return cost;
}
void dfs(int x, int y) {
	//if (visited[x][y])return;
	if (x == d1 && y == d2) {//到达终点
		min_cost = min(now_cost, min_cost);
		return;
	}
	//剪枝
	if (now_cost >= min_cost)return;
	//开始递归遍历dfs
	int oristate = state; int ori_now_cost = now_cost;
	if (x > 0 && !visited[x - 1][y]) {
		now_cost += cal_cost_and_state(x - 1, y);
		visited[x - 1][y] = true;
		dfs(x - 1, y);
		visited[x - 1][y] = false;
		state = oristate;now_cost = ori_now_cost;
	}
	if (y > 0 && !visited[x ][y-1]) {
		now_cost += cal_cost_and_state(x, y - 1);
		visited[x ][y-1] = true;
		dfs(x , y-1);
		visited[x ][y-1] = false;
		state = oristate; now_cost = ori_now_cost;
	}
	if (x<5  && !visited[x + 1][y]) {
		now_cost += cal_cost_and_state(x + 1, y);
		visited[x + 1][y] = true;
		dfs(x + 1, y);
		visited[x + 1][y] = false;
		state = oristate; now_cost = ori_now_cost;
	}
	if (y < 5 && !visited[x ][y+1]) {
		now_cost += cal_cost_and_state(x, y + 1);
		visited[x ][y+1] = true;
		dfs(x, y+1);
		visited[x ][y+1] = false;
		state = oristate; now_cost = ori_now_cost;
	}
}
int main() {

	for (int i = 0; i < 6; i++)
		for (int j = 0; j < 6; j++)
		{
			cin >> a[i][j];
			visited[i][j] = false;
		}
	
	cin >> s1 >> s2 >> d1 >> d2;

	visited[s1][s2] = true;
	dfs(s1, s2);
	visited[s1][s2] = false;
		
	cout << min_cost << endl;
	return 0;
}