01迷宫问题
这题听说有人用并查集做的......很简单的一道题,要注意的就是可能会超时,需要计算一下时间复杂度。这题问的是某一格开始能移动到多少个格子,显然这题要不就用DFS连通块要不就用BFS宽搜一下,这题很好写。但是有一个问题就是注意这个数据规模,m<=100000,如果用bfs的话显然不能每次询问每次bfs,这样真的一定会超时,o(m*N*N),N还是比较大的(N代表可移动的格数),所以肯定会t,这时候就需要用一个amove辅助数组去记录每个位置最多能移动的个数,但是一定要记录连通分量,bfs搜索的时候顺便用连通分量记录下来,这样就避免了o(n*n*N)的算法时间复杂度,有一个地方要注意的是visited标记数组不用清空了,一方面已经搜索过的位置不用再搜索了这个标记数组有点没必要,另一方面visited数组每次清空的话是o(n*n),大约是1000000,最坏清空的话就是o(n*n*n*n),显然这一定会爆时间,10^12。
下面是代码:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <set>
#include <cstring>
#include <queue>
using namespace std;
const int N=1010;
const int M=1000001;
queue<pair<int,int> > qu;
int a[N][N],amove[M],visited[N][N];
int own[N][N],k=1;
int n,m;
int dx[4]= {1,-1,0,0},dy[4]= {0,0,1,-1};
bool inmap(int x,int y)
{
return x>=1&&x<=n&&y>=1&&y<=n;
}
int bfs(int x,int y)
{
int step=0;
if(!own[x][y])
{
k++;
qu.push(make_pair(x,y));
visited[x][y]=1;
while(!qu.empty())
{
pair<int,int> p;
p=qu.front();
int e=a[p.first][p.second];
own[p.first][p.second]=k;
step++;
// cout<<p.first<<"!"<<p.second<<endl;
qu.pop();
for(int i=0; i<4; i++)
{
x=p.first+dx[i];
y=p.second+dy[i];
// cout<<a[2][1]<<" "<<e<<endl;
if(a[x][y]==!e&&!visited[x][y]&&inmap(x,y))
{
visited[x][y]=1;
qu.push(make_pair(x,y));
}
}
}
// cout<<amove[k]<<" "<<k<<" "<<step<<endl;
amove[k]=step;
return 1;
}
return 0;
}
int main()
{
cin>>n>>m;
string s1[N];
for(int i=1; i<=n; i++)
{
cin>>s1[i];
}
for(int i=1; i<=n; i++)
{
for(int j=0; j<n; j++)
{
a[i][j+1]=s1[i][j]-'0';
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(bfs(i,j)){}
else {}
// cout<<endl;
}
}
while(m--)
{
int qa,qb;
cin>>qa>>qb;
cout<<amove[own[qa][qb]]<<endl;
}
return 0;
}