求助,为啥这样写记忆化搜索结果不对呢
查看原帖
求助,为啥这样写记忆化搜索结果不对呢
60925
KKKZOZ楼主2022/11/5 10:55
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

大部分点都是对的,但如上图,有些点没对,这是为啥

2022/11/5 10:55
加载中...