HBQS @ 2024-12-25 20:45:58
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int maxn = 1010;
int mp[maxn][maxn],xx[]={0,0,1,-1},yy[]={1,-1,0,0};
int vis[maxn][maxn];
void bfs();
queue<int>x;
queue<int>y;
int h,n,a,b,cnt;
int main()
{
char ch;
cin>>h>>n;
for(int i = 1;i<=h;i++)
{
for(int j = 1;j<=h;j++)
{
cin>>ch;
mp[i][j] = ch-'0';
}
}
for(int i = 0;i<n;i++)
{
cin>>a>>b;
x.push(a);
y.push(b);
vis[a][b] = 1;
cnt=0;
bfs();
for(int j = 1;j<=h;j++)
{
for(int k = 1;k<=h;k++)
{
if(vis[j][k]) cnt++;
}
}
cout<<cnt<<endl;
memset(vis,0,sizeof(vis));
}
}
void bfs()
{
while(!x.empty())
{
int cx = x.front();
int cy = y.front();
x.pop(),y.pop();
for(int i = 0;i<4;i++)
{
int dx = cx + xx[i];
int dy = cy + yy[i];
if(dx>=1&&dy>=1&&dx<=h&&dy<=h&&!vis[dx][dy])
{
vis[dx][dy] = 1;
x.push(dx);
y.push(dy);
}
}
}
}
/*written by HBQS!*/
这个代码一定会超时 但为什么会wa呢?本来想着看看能拿多少分再优化 结果没超时的都wa了 求救 思路是先起点广搜 将搜过的地方都标记 然后再遍历这个数组 每经历过一个地方就计数器加1
by HBQS @ 2024-12-25 20:54:04
哦 犯病了 要补充一个mp[dx][dy]!=mp[cx][cy] 这下就只剩超时优化了
by HBQS @ 2024-12-25 21:07:00
12.25,21:06ac了 撒花花