记录编号	97549	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 01迷宫	最终得分	100
用户昵称	Dijkstra	是否通过	通过
代码语言	C++	运行时间	0.689 s
提交时间	2014-04-19 15:51:11	内存使用	5.08 MiB

#include<fstream>
#include<queue>
using namespace std;
ifstream fin("maze01.in");
ofstream fout("maze01.out");
struct point{int x,y;};
int style[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int N,M,ans[1000][1000]={{0}},step;
bool map[1000][1000];
queue<point>rec;
queue<point>bfs;
void BFS(int x,int y)
{
	bfs.push((point){x,y});
	int X,Y,i;
	point p;
	ans[x][y]=1;
	step=1;
	while(!bfs.empty())
	{
		p=bfs.front();
		bfs.pop();
		for(i=0;i<4;i++)
		{
			X=p.x+style[i][0];
			Y=p.y+style[i][1];
			if(X<0||X==N||Y<0||Y==N) continue;
			if(map[p.x][p.y]+map[X][Y]!=1) continue;
			if(ans[X][Y]) continue;
			step++;
			bfs.push((point){X,Y});
			rec.push((point){X,Y});
			ans[X][Y]=1;
		}
	}
	while(!rec.empty())
	{
		p=rec.front();
		rec.pop();
		ans[p.x][p.y]=step;
	}
}
int main()
{
	int i,j;
	char ch;
	fin>>N>>M;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
		{
			fin>>ch;
			map[i][j]=int(ch-'0');
		}
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			if(!ans[i][j])
			{
				rec.push((point){i,j});
				BFS(i,j);
			}
	while(M--)
	{
		fin>>i>>j;
		fout<<ans[i-1][j-1]<<endl;
	}
	return 0;
}