走迷宫2（边界跳跃/队列/广搜）

怼烎@ 2023-07-25 09:51 27阅读 0赞

## 走迷宫 ##

先贴题目。

## 描述 ##

Time Limit:1000MS Memory Limit:65535K  
题型: 编程题 语言: 无限制  
描述  
有一个N\*M(N,M<=10)的格子迷宫，1代表该格子为墙，不能通过，0代表可以通过，人在迷宫中可以尝试上下左右四个方向移动。  
另外，在迷宫中如果从左边走出迷宫会回到迷宫最右边一格（只要该格不是墙），行不变，同样，从右边走出迷宫会  
回到迷宫最左边一格，向上走出迷宫会回到迷宫最下边一格，向下走出迷宫会回到迷宫最上边一格。  
现在给定一个迷宫，以及起点和终点，问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。

## 输入格式 ##

该程序为多CASE，第1行为CASE的数量  
每一个CASE，第1行为两个数N（行）和M（列）  
然后N行每行M个数，之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列)

## 输出格式 ##

如题

## 输入样例 ##

2  
4 3  
011  
010  
110  
110  
0 0 3 2  
2 2  
01  
10  
0 0 1 1

## 输出样例 ##

4  
die  
**提示**  
第一个case，可以从（1，0）走到（1，2）  
作者 admin  
我是分割线

## 解题思路： ##

这道题跟经典的走迷宫不同之处就在于可以从一段到另一端探索，因此我们可以针对这个情况特判和特殊处理。每探索一次，我们就对探索的点进行判断，判断是否是越界，即行走到了负一或n,或者列走到了负一或m。如果走到了这种情况，那么我们就可以具体写出入队元素了。

## 贴代码 ##

#include<iostream>
    #include<cstring>
    using namespace std;
    int dx[4]={ 1,-1,0,0},dy[4]={ 0,0,1,-1};
    struct node
    { 
    	int x,y; 
    };
    int v[110][110];
    char a[110][110];
    int n,m;//行和列
    //doors door[110];//声明传送门 
    node in,out;//声明起点和终点 
    int bfs(int x,int y)
    { 
    	node q[10002];
    	int f=0,r=0;
    	v[x][y]=1;
    	q[r++]={ x,y};
    	
    	while(f!=r)
    	{ 
    	   	node temp=q[f++];
    		if(temp.x==out.x&&temp.y==out.y)//走到了出口 
    		{ 
    			//cout<<v[n][m]<<endl;
    			return  v[out.x][out.y]-1;
    		}
    	    
    	    else
    		for(int i=0;i<4;i++)
    		{ 
    			    int cx=temp.x+dx[i];
    			    int cy=temp.y+dy[i];
    			    if(cx==-1&&v[n-1][cy]==0&&a[n-1][cy]=='0')//上
    				{ 
    					q[r++]={ n-1,cy};
    					v[n-1][cy]=v[temp.x][temp.y]+1;
    				 } 
    				 else if(cx==n&&v[0][cy]==0&&a[0][cy]=='0')//下 
    				{ 
    					q[r++]={ 0,cy};
    					v[0][cy]=v[temp.x][temp.y]+1;
    				 } 
    				 else if(cy==-1&&v[cx][m-1]==0&&a[cx][m-1]=='0')//左
    				 { 
    				 	q[r++]={ cx,m-1};
    				 	v[cx][m-1]=v[temp.x][temp.y]+1;
    				  } 
    				  else if(cy==m&&v[cx][0]==0&&a[cx][0]=='0')//右 
    				 { 
    				 	q[r++]={ cx,0};
    				 	v[cx][0]=v[temp.x][temp.y]+1;
    				  } 
    			   else if(cx>=0&&cx<n&&cy>=0&&cy<m&&v[cx][cy]==0&&a[cx][cy]=='0')//没有超出边界 
    			{ 
    				q[r++]={ cx,cy};
    				v[cx][cy]=v[temp.x][temp.y]+1;
    			}
    			 
    		}
    	}
    	return 0;
    	
    }
    
    int main()
    { 
    	int t;
    	cin>>t;
    	while(t--)
    	{ 
    		memset(v,0,sizeof(v));
    		memset(a,0,sizeof(a));
    		cin>>n>>m;//输入迷宫的行和列 
    		for(int i=0;i<n;i++)//输入迷宫 
    		for(int j=0;j<m;j++)
    		cin>>a[i][j];
    		cin>>in.x>>in.y; //输入起点和终点的坐标 
    		cin>>out.x>>out.y;
    		if(in.x==out.x&&in.y==out.y)//特判（多次wa在这里）
    		cout<<0<<endl;
    		else
    		{ 
    			int result=bfs(in.x,in.y);
    		if(result)
    		cout<<result<<endl;
    		else 
    		cout<<"die"<<endl;
    		}
    		
    	}
    	return 0;
    }