题解 | #棋盘游戏#

#include <bits/stdc++.h>
using namespace std;

int a[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; 
int matrix[8][8],vis[8][8];
int mincost=INT_MAX;
int si,sj,ei,ej;

void dfs(int i,int j,int statue,int cost)
{
	if(i>6||i<1||j>6||j<1) return;//超出棋盘范围
	if(cost>mincost) return;//到这步的花费已经大于记录的最小代价，good剪枝 
	if(i==ei+1&&j==ej+1)//到达终点 
	{
		mincost=min(mincost,cost);
		return;
	}
	vis[i][j]=1;
	for(int k=0;k<4;k++)//四个方向走 
	{
		if(vis[i+a[k][0]][j+a[k][1]]==0)
		{
			//cout<<i+a[k][0]<<j+a[k][1]<<endl;
			int thiscost=matrix[i+a[k][0]][j+a[k][1]]*statue;
			dfs(i+a[k][0],j+a[k][1],(thiscost%4)+1,cost+thiscost);
			vis[i+a[k][0]][j+a[k][1]]=0;//回溯 
		}
	}
}

int main(){
	for(int i=1;i<=6;i++)
	for(int j=1;j<=6;j++)
	{
		cin>>matrix[i][j];
	}
	cin>>si>>sj>>ei>>ej;
	dfs(si+1,sj+1,1,0);
	cout<<mincost<<endl;
	return 0;
}