public static int dfs(int x,int y){
if(x==1 && y==1) return 0;
if(mem[x][y]!=-1) return mem[x][y];
int ans=999;
for(int i=0;i<12;i++){
int tx = x+dx[i];
int ty = y+dy[i];
if(tx<1 ||tx>25 ||ty<1 ||ty>25||vis[tx][ty]) continue;
vis[tx][ty]=true;
ans=Math.min(ans,dfs(tx,ty)+1);
vis[tx][ty]=false;
}
return mem[x][y]=ans;
}
main函数中调用的是dfs(x1,y1) 最后矩阵mem的结果如下图
-1 99 2 99 99 3 99 4 99 5 5 6 6 7 99 8 99 9 10 99 99 11 11 99 99
3 99 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 99 11 99 12
2 1 1 3 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 99 11 12 12
2 2 3 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 99 12
99 3 2 4 4 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 99 12
99 3 3 3 3 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12
99 5 4 3 3 4 4 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12
99 4 4 4 4 4 4 4 6 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12
99 5 4 4 4 4 4 5 5 5 5 6 7 7 7 8 8 9 9 10 10 11 11 12 12
99 99 5 5 5 5 5 7 5 5 7 7 6 7 7 8 8 9 9 10 10 11 11 12 12
99 5 5 10 6 5 5 5 5 6 6 6 7 7 7 8 8 9 9 10 10 11 11 12 12
99 6 6 99 6 6 6 6 8 6 6 8 8 7 7 9 8 9 9 10 10 11 11 12 12
99 9 7 6 6 6 6 6 6 6 6 7 7 7 8 9 9 9 9 10 10 11 11 12 12
99 99 7 7 7 7 7 9 7 7 9 9 7 8 9 8 8 10 9 10 10 11 11 12 12
8 7 7 10 8 7 7 7 7 7 7 7 9 8 8 8 9 10 9 10 10 11 11 12 12
99 8 8 8 8 8 8 8 99 8 8 8 10 8 8 10 10 9 9 11 12 11 11 13 12
99 9 9 8 8 8 8 8 8 8 8 8 8 8 10 10 10 9 10 11 11 11 11 13 12
99 11 99 9 9 9 13 11 9 9 11 11 9 9 11 9 9 11 11 10 10 12 13 12 12
10 9 9 10 9 9 9 9 9 9 9 9 11 9 9 9 11 11 10 11 11 12 11 12 12
99 10 10 10 99 10 10 10 12 10 10 10 99 10 10 99 12 10 10 12 12 11 11 99 99
10 11 12 10 10 10 10 10 10 10 10 10 10 10 12 12 10 10 12 12 11 12 12 99 99
11 99 11 11 11 11 11 11 11 11 11 11 11 11 12 11 11 11 13 11 11 12 12 12 12
13 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 13 11 11 12 13 12 12 13 13
99 99 12 99 12 13 12 13 12 13 12 13 13 12 12 12 14 12 12 12 12 12 12 13 13
99 99 12 12 12 12 12 12 12 12 12 12 12 12 99 12 13 12 13 12 13 13 13 13 13
大部分点都是对的,但如上图,有些点没对,这是为啥