Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define M 505
- bool visited[M][M];
- int cell[M][M];
- int fx[]={1,-1,0,0};
- int fy[]={0,0,1,-1};
- int m,n;
- int mark[M][M];
- int bfs(int x,int y)
- {
- visited[x][y]=true;
- pair<int,int>p,p1;
- int count=0;
- queue<pair<int,int> >q;
- q.push(make_pair(x,y));
- if(mark[x][y]==1)
- count++;
- //dis[x][y]=1;
- else
- count=0;
- //dis[x][y]=0;
- while(!q.empty())
- {
- p=q.front();
- q.pop();
- for(int i=0;i<4;i++)
- {
- int tx=p.first+fx[i];
- int ty=p.second+fy[i];
- if(tx>=0 && tx<m && ty>=0 && ty<n){
- if(visited[tx][ty]==false && mark[tx][ty]!=-1)
- {
- if(mark[tx][ty]==1){
- count++;
- }
- visited[tx][ty]=true;
- q.push(make_pair(tx,ty));
- }
- }
- }
- }
- return count;
- }
- int main()
- {
- int t,kase=0;
- scanf("%d",&t);
- while(kase<t)
- {
- int q,i,j;
- //char c;
- scanf("%d %d %d",&m,&n,&q);
- for(i=0;i<m;i++)
- {
- getchar();
- for(j=0;j<n;j++)
- {
- char c;
- scanf(" %c",&c);
- //getchar();
- if(c=='#'){
- //visited[i][j]=true;
- mark[i][j]=-1;
- //cell[i][j]=-1;
- }
- else if(c=='.')
- {
- mark[i][j]=0;
- //cell[i][j]=1;
- //visited[i][j]=false;
- }
- else if(c=='C')
- {
- mark[i][j]=1;
- }
- }
- }
- printf("Case %d:\n",kase+1);
- int ans;
- memset(cell,-1,sizeof cell);
- while(q--)
- {
- int x,y;
- scanf("%d %d",&x,&y);
- if(cell[x-1][y-1]!=-1)
- {
- ans=cell[x-1][y-1];
- }
- else
- {
- ans=0;
- memset(visited,false,sizeof visited);
- memset(cell,-1,sizeof cell);
- x--,y--;
- ans=bfs(x,y);
- for(i=0;i<m;i++)
- {
- for(j=0;j<n;j++)
- {
- if(visited[i][j]==true)
- {
- cell[i][j]=ans;
- }
- }
- }
- }
- printf("%d\n",ans);
- }
- memset(mark,0,sizeof mark);
- //memset(cell,-1,sizeof cell);
- kase++;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment