leetcode505.迷宫2

浅浅的花香味﹌ 2022-09-11 13:18 53阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_12_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_11_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_10_color_FFFFFF_t_70_g_se_x_16]  
思路

1.  这个题中，由于要找最近的距离，所以点是可以重复跑的，每次选最小距离，根据最小距离进行递归
2.  注意还是不撞墙不能停的

代码

void dfs(int** maze, int mazeSize, int mazeColSize, int startx, int starty, int endx, int endy,int k,int len[][100]){ 
        if(startx<0||starty<0||startx>mazeSize||starty>mazeColSize||maze[startx][starty]==1){ 
            return;//撞墙 停
        }
        int up=startx-1;
        int down =startx+1;
        int left = starty-1;
        int right = starty+1;
        int t=0;
        while(up>=0&&maze[up][starty]!=1){ 
            up--;
        }
        t=abs(up+1-startx);
        if(len[up+1][starty]>len[startx][starty]+t){ //只有当前的路径是最小的距离时，该路径才进行递归，否则该路径无效，但是不能返回，因为有四个方向，一个方向不行，还可能其他方向行，这个地方卡好久
            len[up+1][starty]=len[startx][starty]+t;
            dfs(maze, mazeSize, mazeColSize, up+1, starty, endx, endy, k+t,len);
        }
        while(down<mazeSize&&maze[down][starty]!=1){ 
            down++;
        }
        t=abs(down-1-startx);
        if(len[down-1][starty]>len[startx][starty]+t){ 
            len[down-1][starty]=len[startx][starty]+t;
            dfs(maze, mazeSize, mazeColSize, down-1, starty, endx, endy, k+t,len);
        }
            
        
        while(left>=0&&maze[startx][left]!=1){ 
            left--;
        }
        t= abs(left+1-starty);
        if(len[startx][left+1]>len[startx][starty]+t){ 
            len[startx][left+1]=len[startx][starty]+t;
            dfs(maze, mazeSize, mazeColSize, startx, left+1, endx, endy, k+t,len);
        }
            
    
        while(right<mazeColSize&&maze[startx][right]!=1){ 
            right++;
        }
        t =abs(right-1-starty);
        if(len[startx][right-1]>len[startx][starty]+t){ 
            len[startx][right-1]=len[startx][starty]+t;
            dfs(maze, mazeSize, mazeColSize, startx, right-1, endx, endy, k+t,len);
        }
            
    }
    int shortestDistance(int** maze, int mazeSize, int* mazeColSize, int* start, int startSize, int* destination, int destinationSize){ 
        int startx=start[0];
        int starty=start[1];
        int endx = destination[0];
        int endy = destination[1];
        int k =0,i,j;
        //int len=10000;
        int len[mazeSize][100];
        for(i=0;i<mazeSize;i++){ 
            for(j=0;j<100;j++){ 
                len[i][j]=10000;
            }
        }
        len[startx][starty]=0;
        dfs(maze,mazeSize,*mazeColSize,startx,starty,endx,endy,k,len);
        if(len[endx][endy]==10000)
            return -1;
        return  len[endx][endy];
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3ad506f2a06e461e8454ea86772fbd74.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/523375f18813480c9ae6c4bf8c8bc069.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/baa30e2811a54ac0bdf74544f2348a51.png