1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d",n)
#define pfc(c) printf(c)
#define fi(i,s,t) for(int i=s;i<t;i++)
#define fd(s,t) for(int i=s-1;i>=t;i--)
#define mem(a,c) memset(a,c,sizeof(a))
const int INF=0x3f3f3f3f;
const int MAX=1000+10;
int n,m,x,y,vis[MAX][MAX],rec[100005];
char a[MAX][MAX];
int aw[4][2]={-1,0,0,1,1,0,0,-1},ans;
bool judge(int x,int y){
if(x<1 || x>n || y<1 || y>n ) return false;
return true;
}
struct node{
int x,y;
node(int _x,int _y){
x=_x;y=_y;
}
};
queue <node> q;
int bfs(node t,int tag){
if(rec[vis[t.x][t.y]]!= 0)
return rec[vis[t.x][t.y]];
q.push(t);
vis[t.x][t.y]=tag;
ans =0;
while(!q.empty()){
node c = q.front();
q.pop();
ans ++;
fi(i,0,4){
int tx= c.x + aw[i][0],ty= c.y + aw[i][1];
if(judge(tx,ty) && vis[tx][ty]<tag && a[tx][ty]!=a[c.x][c.y]){
q.push(node(tx,ty));
vis[tx][ty]=tag;
}
}
}
return rec[vis[t.x][t.y]]=ans;
}
int main(){
freopen("in","r",stdin);
sf(n);sf(m);
fi(i,1,n+1)
scanf("%s",a[i]+1);
fi(i,1,m+1){
sf(x);sf(y);
pf(bfs(node(x,y),i));pfc("\n");
}
return 0;
}
|