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

大赞!继续加油!:)

0
0

玩转算法系列--图论精讲(Java版)

30+小时系统学习,bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

查看课程