70分TLE求助
  • 板块P1141 01迷宫
  • 楼主tonyG
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/11/1 17:16
  • 上次更新2023/11/5 09:17:29
查看原帖
70分TLE求助
128353
tonyG楼主2020/11/1 17:16

直接上代码!

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;
struct point
{
	int x,y;
	point(int x=0,int y=0)
	{
		this->x=x;
		this->y=y;
	}
};
int n,m,ans;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
char c;
bool map[1005][1005],flag[1005][1005];
int sx,sy;
void bfs()
{
	queue <point> q;
	q.push(point(sx,sy));
	flag[sx][sy]=1;
	
	while(!q.empty())
	{
		point cur=q.front();
		q.pop();
//		if(flag[cur.x][cur.y]==1)
//		    continue;
		for(int i=0;i<4;i++)
		{
			int x1=cur.x+dx[i];
			int y1=cur.y+dy[i];
			if(x1>=1&&y1>=1&&x1<=n&&y1<=n&&map[cur.x][cur.y]!=map[x1][y1]&&flag[x1][y1]==0)
			{
				flag[x1][y1]=1;
				q.push(point(x1,y1));
			}
		}
	}
}
int main()
{
int i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
{
	for(j=1;j<=n;j++)
	{
		//cin>>c;
		scanf(" %c",&c);
		map[i][j]=c-'0';
	}
}
int x,y;
while(m--)
{
	ans=0;
	memset(flag,0,sizeof(flag));
	//cin>>sx>>sy;
	scanf("%d%d",&sx,&sy);
	bfs();
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(flag[i][j]==1)
			    ans++;
		}
	}
	cout<<ans<<endl;
}
return 0;
}
/*
2 1
01
10
1 1
*/
2020/11/1 17:16
加载中...