KY98 棋盘游戏

DFS 深搜板子

#include<bits/stdc++.h>

using namespace std;

#define ll long long

struct Node {
    int m, n;
};

int n;
int res = 100010;
int v[6][6];
int a, b, c, d;
bool st[6][6];
ll pp[6][6];
int xi[4] = {1, 0, -1, 0};
int yi[4] = {0, 1, 0, -1};

void dfs(int x, int y, int state, int cow){
	if(x == c && y == d){
		res = min(res, cow);
		return ;
	}
	if(cow > res) return ;
	st[x][y] = true;  //防止搜回去 
	for(int i = 0; i < 4; i ++ ){
		int xx = x + xi[i];
		int yy = y + yi[i];
		if(xx < 0 || xx > 5 || yy < 0 || yy > 5 || st[xx][yy]) continue;
		int c = v[xx][yy] * state;
		int iu = (c % 4) + 1;
		dfs(xx, yy, iu, cow + c);
		st[xx][yy] = false;
	}
}

int main() {
    for(int i = 0; i < 6; i ++ ){
		for(int j = 0; j < 6; j ++ ){
			cin>>v[i][j];
		}
	}
	memset(st, 0, sizeof st);
	cin>>a>>b>>c>>d;
	dfs(a, b, 1, 0);
	cout<<res<<endl;
    return 0;
}