题目描述
由空地和墙组成的迷宫中有一个球，球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。给定球的起始位置、目的地和迷宫。判断球能否在目的地停下。
思路分析：
迷宫由一个0和1的二维数组组成，1表示墙壁，0代表空地。你可以假设迷宫的边缘都是墙壁，防止小球出界，起始位置和目的地的坐标通过行号和列好给出。该题特别注意，小球是向一个方向运动，直到停下为止，并不是一次只运动一格。
示例一：
输入 1: 迷宫由以下二维数组表示0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4) 输入 3: 目的地坐标 (rowDest, colDest) = (4, 4)输出: true解析: 一个可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。示例二：
输入 1: 迷宫由以下二维数组表示0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4) 输入 3: 目的地坐标 (rowDest, colDest) = (3, 2)输出: false解析: 没有能够使球停在目的地的路径。注意: 迷宫中只有一个球和一个目的地。 球和目的地都在空地上，且初始时它们不在同一位置。 给定的迷宫不包括边界 (如图中的红色矩形), 但你可以假设迷宫的边缘都是墙壁。 迷宫至少包括2块空地，行数和列数均不超过100。class Solution{ public:int dirx[4] = {0,1,0,-1},diry[4]={1,0,-1,0};int visit[101][101],ex,ey,n,m;bool hasPath(vector<vector<int>>& maze,vector<int>& start,vector<int>& destination){//把start和destination的输入当成了一个一维数组int sx=start[0],sy=start[1];//起始坐标n=maze.size();//整个地图的大小m=maze[0].size();//地图一行的大小ex=destination[0],ey=destination[1]; //终点坐标memset(visit,0,sizeof(visit));//分配一个101*101的内存空间给visit数组visit[sx][sy]=1;//在visit当中标记起始点的坐标if(DFS(sx,sy,maze)) return true;//如果能在目的地停下，则返回trueelse return false;}bool DFS(int x,int y,const vector<vector<int>> &maze){if(x==ex && y==ey) return true;//抵达终点 for(int i=0;i<4;i++){int dx=x+dirx[i];int dy=y+diry[i];while(dx>=0 && dx<n && dy>=0 && dy<m && maze[dx][dy]==0)//保持当前方向，遇到障 //碍物之前一直往此方向走{dx=dx+dirx[i];dy=dy+diry[i];}//因为上述while循环多执行了一步，走到了障碍物那个位置，故需要退一步。dx=dx-dirx[i];dy=dy-diry[i];if(visit[dx][dy]) continue;visit[dx][dy]=1;bool flag = DFS(dx,dy,maze);//递归调用if(flag) return true;}return false;} }
最短路径-迷宫问题（DFS---迷宫问题_牛客题霸_牛客网）
#include<stdio> int n,m,a[105][105],dx[]={0,-1,1,0},dy[]={1,0,0,-1}; struct node{int x,y;}; bool vis[105][105],g=false; vector<node> q;void dfs(int x,int y) {if(g) return;//如果到达终点，则输出存储到q栈当中的路径if(x==n-1 && y==m-1) {g=true;for(int i=0;i<(int)q.size();i++)printf("(%d,%d)\n",q[i].x,q[i].y);//cout<<'('<<q[i].x<<','<<q[i].y<<')'<<endl;return;}if(x>0 && x<n && y>0 && y<m && vis[x][y]==0){vis[x][y]=true;q.push_back({x,y});dfs(x,y);q.pop_back();vis[x][y]=false;} }int main(){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",&a[i][j]);q.push_back({0,0});vis[0][0]=true;dfs(0,0); }
