洛谷题集——01迷宫（dfs、bfs）

古城微笑少年丶 2023-03-13 05:26 28阅读 0赞

### 01迷宫 ###

有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。  
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入格式  
第1行为两个正整数n,m。  
下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。  
接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。

输出格式  
m行，对于每个询问输出相应答案。

输入输出样例  
输入  
2 2  
01  
10  
1 1  
2 2  
输出  
4  
4

--------------------

#### BFS版本 ####

该题是查询某一块符合条件的个数，而且是多组输入。  
若用到单纯BFS的思路的话，很容易造成重复查询的情况，导致超时。  
为了避免超时，这里应当用BFS+记忆化剪枝的方式提高效率。

#include<bits/stdc++.h>
    using namespace std;
    int mg[1010][1010], n, m;
    
    //防止重复记格 
    bool flag[1010][1010]={ false};
    
    int X[4]={ 0, 0, -1, 1};
    int Y[4]={ -1, 1, 0, 0};
    
    struct node{ 
    	int a;
    	int b;
    }Node, top;
    
    bool judge(int xi, int yi, int x, int y)
    { 
    	if(x<=0||y<=0||x>n||y>n)
    	return false;
    	if((mg[xi][yi]==1&&mg[x][y]==0)||(mg[xi][yi]==0&&mg[x][y]==1))
    	return true;	
    	return false;
    }
    
    map<int, int> mm;
    
    int main()
    { 
    	char ch;
    	cin>>n>>m;
    	
    	for(int i=1; i<=n; i++)
    	for(int j=1; j<=n; j++)
    	{ 
    		cin>>ch;
    		if(ch=='0')
    		mg[i][j]=0;
    		else
    		mg[i][j]=1;
    	}
    	
    	while(m--)
    	{ 
    		int x, y, sum=0;
    		cin>>x>>y;
    		if(mg[x][y]==0||mg[x][y]==1)
    		{ 
    			queue<node> q;
    			Node.a=x;
    			Node.b=y;
    			q.push(Node);
    			while(!q.empty())
    			{ 
    				top=q.front();
    // cout<<top.a<<" "<<top.b<<endl;
    				int xi=top.a;
    				int yi=top.b;
    				for(int i=0; i<4; i++)
    				{ 
    					if(judge(xi, yi, xi+X[i], yi+Y[i]))
    					{ 
    						Node.a=xi+X[i];
    						Node.b=yi+Y[i];
    						q.push(Node);
    					}
    				}
    			// 防止重复记格 
    				if(flag[xi][yi]==false)
    					sum++;
    				flag[xi][yi]=true;
    				mg[xi][yi]=m+100010;
    				q.pop();
    			}
    			mm[m+100010]=sum;
    		}
    /* for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) cout<<mg[i][j]<<" "; cout<<endl; }*/
    		cout<<mm[mg[x][y]];
    		if(m!=0) cout<<endl;
    	}
    	
    	return 0;
    }

##### DFS版本 #####

相比与该题的BFS版本，个人认为DFS思路较为巧妙，而BFS版本就是单纯的模板改良。  
主要思路：将要查询的方格i，通过DFS试探的方式查找出符合条件该方块周围符合的方块数，同时利用flag二维数组标记访问过的方格，防止重复访问（剪枝），并最终结果记录在ans\[i\]中。

#include<bits/stdc++.h>
    using namespace std;
    int n, m;
    int flag[1010][1010];
    int mg[1010][1010];
    int ans[100010];
    int X[4]={ 0, 0, 1, -1};
    int Y[4]={ 1, -1, 0, 0};
    
    void dfs(int x, int y, int i)
    { 
    	if(x<1||y<1||x>n||y>n) return;
    	ans[i]++;
    	flag[x][y]=i;
    	for(int j=0; j<4; j++)
    	if(mg[x+X[j]][y+Y[j]]!=mg[x][y]&&flag[x+X[j]][y+Y[j]]==-1)
    		dfs(x+X[j], y+Y[j], i);
    }
    
    int main()
    { 
    	cin>>n>>m;
    	for(int i=1; i<=n; i++)
    	for(int j=1; j<=n; j++)
    	{ 
    		char ch;
    		cin>>ch;
    		if(ch=='1') mg[i][j]=1;
    		else mg[i][j]=0;
    	}
    	
    	memset(flag, -1, sizeof(flag));
    	memset(ans, 0, sizeof(ans));
    	for(int i=0; i<m; i++)
    	{ 
    		int x, y;
    		cin>>x>>y;
    		if(flag[x][y]==-1)
    		{ 
    			flag[x][y]=i;
    			dfs(x, y, i);
    		}
    		else
    			ans[i]=ans[flag[x][y]];
    	}
    	for(int i=0; i<m; i++)
    	{ 
    	    cout<<ans[i];
    	    if(i!=m-1) cout<<endl;
    	}
    	return 0;
    }

#### 总结 ####

在该题中，在运行效率上dfs代码比bfs代码要高，但在存储空间上bfs代码比dfs代码要小，各有所长。

希望能够将自己的一些学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白。