网格图回溯模板
相关代码
public class Main {
static int dx[] = { -1, 1, 0, 0 };
static int dy[] = { 0, 0, -1, 1 };
static boolean st[][] = new boolean[110][110];
static int res = 0;
public static void main(String[] args) {
}
public static void dfs(int a, int b, int m, int n, int k) {
// 终止条件
if (sum(a, b) > k)
return;
res++;
//如果(a,b)不符合终止条件,则
st[a][b]=true;
// 状态转移
for (int i = 0; i < 4; i++) {
int x = a + dx[i];
int y = b + dy[i];
//首先对(x,y)的值判断是否合法,和判断st[x][y]==true,和判断该点是否合法。
if(x<0||x>=m||y<0||y>=n) continue;
if(st[x][y]==true) continue;
//筛选完成后,进入下一层,即dfs
dfs(x,y,m,n,k);
}
//如果该题中存在回溯,则此位置写 st[x][y]=false;
}
}