吸氧一个样,崩溃
#include <bits/stdc++.h>
using namespace std;
int n, m, level = 0, sum, dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, -1, 1}, sa, sb, ans, a[1000000];
struct point{
int x, y, island_id;
bool is_island, vis;
bool check(){
return x >= 0 && x < n && y >= 0 && y < n;
}
}c[1000][1000], now, t;
queue <point>q;
/*void ready(){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
c[i][j].vis = false;
}
}
}*/
int main(){
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++){
scanf("\n");
for(int j = 0; j < n; j++){
c[i][j].x = i;
c[i][j].y = j;
c[i][j].vis = false;
c[i][j].is_island = (bool)(getchar() - '0');
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(!c[i][j].vis){
sum = 0;
level++;
c[i][j].island_id = level;
t.island_id = level;
q.push(c[i][j]);
while(!q.empty()){
now = q.front();
q.pop();
for(int i = 0; i < 4; i++){
t = now;
t.x += dx[i];
t.y += dy[i];
if(t.check() && !c[t.x][t.y].vis && c[t.x][t.y].is_island == !now.is_island){
c[t.x][t.y].island_id = level;
c[t.x][t.y].vis = true;
q.push(c[t.x][t.y]);
sum++;
}
}
}
a[level] = sum;
// ready();
}
}
}
for(int i = 0; i < m; i++){
ans = 0;
scanf("%d%d", &sa, &sb);
sa--;
sb--;
if(a[c[sa][sb].island_id] != 0){
ans = a[c[sa][sb].island_id];
}
else{
for(int j = 0; j < n; j++){
for(int k = 0; k < n; k++){
if(c[sa][sb].island_id == c[j][k].island_id){
ans++;
}
}
}
a[c[sa][sb].island_id] = ans;
}
printf("%d\n", ans);
}
return 0;
}
啊啊啊啊啊啊