Chitose_ @ 2024-01-17 20:44:03
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1005;
int n,m,x,y;
bool vis[maxn][maxn];
char s[maxn][maxn];
int a[maxn][maxn],ans[maxn][maxn],cnt;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
struct node{
int x,y;
node(int xx1,int yy1){
x=xx1; y=yy1;
}
};
queue<node> q;
int xx,yy,dp[maxn][maxn],dr[maxn*maxn],dc[maxn*maxn];
int bfs(){
if(dp[x][y]!=-1) return dp[x][y];
q.push(node(x,y));
dr[++cnt]=x; dc[cnt]=y;
while(!q.empty()){
node nod=q.front(); q.pop();
for(int i=0;i<4;i++){
xx=nod.x+dx[i]; yy=nod.y+dy[i];
if(xx>=1 && xx<=n && yy>=1 && yy<=n && a[xx][yy]!=a[nod.x][nod.y] && !vis[xx][yy]){
q.push(node(xx,yy));
vis[xx][yy]=true;
dr[++cnt]=xx; dc[cnt]=yy;
}
}
}
return cnt;
}
signed main(){
cin>>n>>m;
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>s[i][j];
a[i][j]=s[i][j]-'0';
}
}
for(int k=1;k<=m;k++){
memset(vis,false,sizeof(vis));
cnt=0;
scanf("%lld%lld",&x,&y);
vis[x][y]=true;
printf("%lld\n",bfs());
for(int i=1;i<=cnt;i++){
dp[dr[i]][dc[i]]=cnt;
}
}
return 0;
}by Y_QWQ_Y @ 2024-01-17 20:51:51
@Bxiay 本题 bfs 似乎做不了，建议记忆化搜索
#include <bits/stdc++.h>
using namespace std;
int n, m, f[1001][1001], ans[100001];
char s[1001][1001];
void dfs (int x, int y, int z, int now)
{
if (x < 0 || x >= n || y < 0 || y >= n || f[x][y] != -1 || s[x][y] - '0' != z)return;
f[x][y] = now;
++ ans[now];
if (z)z = 0;
else z = 1;
dfs (x - 1, y, z, now);
dfs (x + 1, y, z, now);
dfs (x, y - 1, z, now);
dfs (x, y + 1, z, now);
}
signed main()
{
memset (f, -1, sizeof (f));
scanf ("%d %d", &n, &m);
for (int i = 0; i < n; ++ i)cin >> s[i];
for (int i = 0; i < m; ++ i)
{
int x, y, z;
scanf ("%d %d", &x, &y);
-- x;
-- y;
z = s[x][y] - '0';
if (f[x][y] == -1)dfs (x, y, z, i);
else ans[i] = ans[f[x][y]];
}
for (int i = 0; i < m; ++ i)printf ("%d\n", ans[i]);
return 0;
}by Chitose_ @ 2024-01-17 20:59:44
@Y_QWQ_Y 先生大义