leetcode490. 迷宫

雨点打透心脏的1/2处 2022-09-11 10:20 141阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_13_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_13_color_FFFFFF_t_70_g_se_x_16 1]  
思路

1.  注意是撞到墙才停止滚动，四个方向上都能滚动
2.  可能会滚到重复的停止位置，如果停到重复的位置就是无法滚到终点，所以标记的是停止的位置，路径是可以交叉的，如图
3.  不能给停止的位置标记为1，如果滚动一次刚好在终点旁边，那么第二次就会在终点停止，但是这次是错误的  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_7_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]

代码

bool dfs(int** maze, int mazeSize, int mazeColSize, int startx, int starty, int endx, int endy){ 
    	//判断停止位置
        if(startx<0||starty<0||startx>=mazeSize||starty>= mazeColSize||maze[startx][starty] == 1||maze[startx][starty] == 2)
            return false;
        if(startx==endx&&starty==endy){ 
            return true;
        }
     	//停止位置标记
        maze[startx][starty] = 2;
        //从上下左右四个方向开始
        int up = startx-1;
        int down = startx+1;
        int left = starty-1;
        int right = starty+1;
        //向上一直到墙，或者超出范围，其实也是墙停止
        while(up>=0&&maze[up][starty]!=1){ 
            up--;
        }
        //从该停止位置开始，由于up是在墙时出循环，所以回退1，对该停止位置进行dfs
        if(dfs(maze,mazeSize, mazeColSize, up+1, starty, endx, endy))
            return true;
    
        while(down<mazeSize&&maze[down][starty]!=1){ 
            down++;
        }
        if(dfs(maze,mazeSize, mazeColSize, down-1, starty, endx, endy))
            return true;
    
        while(left>=0&&maze[startx][left]!=1){ 
            left--;
        }
        if(dfs(maze,mazeSize, mazeColSize, startx, left+1, endx, endy))
            return true;
    
        while(right<mazeColSize&&maze[startx][right]!=1){ 
            right++;
        }
        if(dfs(maze,mazeSize, mazeColSize, startx, right-1, endx, endy))
            return true;
    
        return  false;
    }
    
    bool hasPath(int** maze, int mazeSize, int* mazeColSize, int* start, int startSize, int* destination, int destinationSize){ 
        int startx = start[0],starty=start[1];
        int endx = destination[0],endy = destination[1];
    
        return dfs(maze, mazeSize, *mazeColSize, startx, starty, endx, endy);
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b0bdcbd4c4f4410d9960172b31702776.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_13_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/752c99e427b94842a7c130926fb6bb78.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_7_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ad6b0e07ffd54b12baa73fb147c38802.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/2acb88db403d44d0849edc3d8fb47a41.png