LC980 DFS回溯的记忆化搜索+状态压缩优化问题
来源:7-7 实现滑动谜题
慕田峪2135618
2024-04-08
已经找到了问题所在,谢谢。
修正后的代码如下。
class Solution {
int[][] grid;
int R,C;
int endX,endY;
int steps=0;
HashMap<Integer,Integer> map=new HashMap<>();
public int uniquePathsIII(int[][] grid) {
int startX=0,startY=0;
this.grid=grid;
R=grid.length;
C=grid[0].length;
for (int i=0;i<R;i++){
for (int j=0;j<C;j++){
if (grid[i][j]==1){
startX=i;
startY=j;
} else if (grid[i][j]==2){
endX=i;
endY=j;
steps++;
} else if (grid[i][j]==0){
steps++;
}
}
}
return dfs(startX,startY,0,0);
}
private int dfs(int x,int y,int step,int visitKey){
int loc=x*C+y;
int bitKey=1<<loc;
if (x<0 || x>=R || y<0 || y>=C || (visitKey & bitKey)==bitKey || grid[x][y]==-1){
return 0;
}
if (x==endX && y==endY && step==steps){
return 1;
}
visitKey+=bitKey;
int state=loc+R*C*visitKey;
if (map.containsKey(state)){
return map.get(state);
}
int res=0;
res+=dfs(x+1,y,step+1,visitKey);
res+=dfs(x-1,y,step+1,visitKey);
res+=dfs(x,y+1,step+1,visitKey);
res+=dfs(x,y-1,step+1,visitKey);
map.put(state,res);
return res;
}
}```
写回答
1回答
-
liuyubobobo
2024-04-18
大赞!继续加油!:)
00
相似问题
关于9-9,记忆化搜索
回答 1
回溯
回答 1