Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //============================================================================
- // Name : ACM
- // Author : Tarango Khan
- // Team : BRACU Byteheads
- //============================================================================
- #include <bits/stdc++.h>
- using namespace std;
- #define Size 100005
- #define Mod 1000000007
- #define INF 999999999999999
- char Mat[1001][1001];
- int R,C,K;
- int DP[1001][1001];
- bool visited[1001][1001];
- int dx[] = {1,-1,0,0};
- int dy[] = {0,0,1,-1};
- int cnt = 0;
- void DFS1(int r,int c){
- visited[r][c] = true;
- for(int i = 0;i<4;i++){
- int rr = dx[i]+r;
- int cc = dy[i]+c;
- if(Mat[rr][cc] == '*'){
- cnt++;
- continue;
- }
- if(visited[rr][cc] == true) continue;
- DFS1(rr,cc);
- }
- }
- void DFS2(int r,int c){
- if(DP[r][c] != -1){
- return;
- }
- DP[r][c] = cnt;
- for(int i = 0;i<4;i++){
- int rr = dx[i]+r;
- int cc = dy[i]+c;
- if(Mat[rr][cc] == '*'){
- continue;
- }
- DFS2(rr,cc);
- }
- }
- int main() {
- int x,y;
- scanf("%d %d %d",&R,&C,&K);
- for(int i = 0;i<R;i++){
- scanf("%s",Mat[i]);
- }
- memset(DP,-1,sizeof(DP));
- memset(visited,false,sizeof(visited));
- for(int i = 0;i<K;i++){
- scanf("%d %d",&x,&y);
- x--;y--;
- cnt = 0;
- if(DP[x][y] != -1){
- cnt = DP[x][y];
- }else{
- DFS1(x,y);
- DFS2(x,y);
- }
- printf("%d\n",cnt);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment