Nulluer @ 2024-10-19 12:24:36
#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
bool a[1005][1005], vis[1005][1005];
int jy[1005][1005];
int py[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
struct node {
int x, y;
};
queue<node> s;
int bfs(int x, int y) {
queue<node> q;
s.push((node) {
x, y
});
q.push((node) {
x, y
});
vis[x][y] = 1;
while (!q.empty()) {
int tx = q.front().x;
int ty = q.front().y;
q.pop();
++ans;
for (int i = 0; i < 4; ++i) {
int ttx = tx + py[i][0];
int tty = ty + py[i][1];
if (ttx <= 0 || tty <= 0 || ttx > n || tty > n || vis[ttx][tty]) {
continue;
} else if (!(a[tx][ty] ^ a[ttx][tty])) {
continue;
}
vis[ttx][tty] = 1;
q.push((node) {
ttx, tty
});
s.push((node) {
ttx, tty
});
}
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
char t;
cin >> t;
a[i][j] = t - '0';
}
}
while (m--) {
int tx, ty;
cin >> tx >> ty;
if (jy[tx][ty]) {
cout << jy[tx][ty] << endl;
continue;
} else {
cout << bfs(tx, ty) << endl;
memset(vis, 0, sizeof(vis));
while (!s.empty()) {
jy[s.front().x][s.front().y] = ans;
s.pop();
}
ans = 0;
}
}
return 0;
}by YUQI_George @ 2024-10-31 20:24:05
不用记忆话，联通快
这是代码：
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
int fx[4]={0,1,0,-1};
int fy[4]={1,0,-1,0};
int n,m,color,cnt;
int a[1010][1010],f[1010][1010],ans[1000010];
void bfs(int x,int y){
queue<int>h;
queue<int>l;
h.push(x);
l.push(y);
f[x][y]=color;
while(!h.empty()){
for(int i=0;i<4;i++){
int tx=fx[i]+h.front();
int ty=fy[i]+l.front();
if(tx>=1&&ty>=1&&tx<=n&&ty<=n&&!f[tx][ty]&&a[tx][ty]!=a[h.front()][l.front()]){
h.push(tx);
l.push(ty);
f[tx][ty]=color;
}
}
h.pop();
l.pop();
cnt++;
}
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
char x;
cin>>x;
if(x=='1') a[i][j]=1;
else a[i][j]=0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!f[i][j]){
color++;
bfs(i,j);
ans[color]=cnt;
cnt=0;
}
}
}
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
cout<<ans[f[x][y]]<<endl;
}
return 0;
}