Competitive_Programming/AMR11J.cpp at master · apsc/Competitive_Programming · GitHub

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<stdio.h>
int m,n;
char a[501][501];
int time[501][501]={0},visited[501][501]={0};
struct queue{
       int x,y;
}q[260000];
int isValid(int p,int q){
     if(p>=m||q>=n||p<0||q<0||a[p][q]=='#')return 0;
     else return 1;
}
int main(){
    int t,posx[]={-1,1,0,0},posy[]={0,0,-1,1},rear,front,xi,yi,xf,yf;
    char temp[502];
    scanf("%d",&t);
    while(t--){
               rear=0;front=0;
               scanf("%d%d",&m,&n);
               for(int i=0;i<m;i++){
                       scanf("%s",&temp);
                       for(int j=0;j<n;j++){
                               a[i][j]=temp[j];
                               if(a[i][j]!='.'&&a[i][j]!='#'){
                                                            q[rear].x=i;
                                                            q[rear].y=j;
                                                            time[i][j]=0;
                                                            //q[rear].time=0;
                                                            rear++;
                                                            visited[i][j]=1;
                                                            //printf("%c\n",a[i][j]);
                               }
                       }
               }
               while(front<=rear){
                                  xi=q[front].x;
                                  yi=q[front].y;
                                  front++;
                                  if(a[xi][yi]=='*'||a[xi][yi]=='#')continue;
                                  for(int i=0;i<4;i++){
                                          xf=xi+posx[i];
                                          yf=yi+posy[i];

                                          if(visited[xf][yf]==1&&isValid(xf,yf)==1){
                                                              if(a[xf][yf]==a[xi][yi])continue;
                                                              else if(time[xi][yi]+1==time[xf][yf]){
                                                                        //printf("%c at %d,%d just got cut by %c at %d,%d\n",a[xf][yf],xf,yf,a[xi][yi],xi,yi);
                                                                        a[xf][yf]='*';
                                                                        continue;
                                                              }
                                                              else if(time[xi][yi]+1>time[xf][yf])continue;
                                                              else if(time[xi][yi]+1<time[xf][yf]){
                                                                                                   a[xf][yf]=a[xi][yi];
                                                                                                   time[xf][yf]=time[xi][yi]+1;
                                                                                                   continue;
                                                              }
                                          }
                                          if(isValid(xf,yf)==1){
                                                             q[rear].x=xf;
                                                             q[rear].y=yf;
                                                             time[xf][yf]=time[xi][yi]+1;
                                                             rear++;
                                                             a[xf][yf]=a[xi][yi];
                                                             visited[xf][yf]=1;
                                          }
                                  }
               }
               for(int i=0;i<m;i++){
                       for(int j=0;j<n;j++){
                               printf("%c",a[i][j]);
                               visited[i][j]=0;time[i][j]=0;
                       }
                       printf("\n");
               }
    }
    return 0;
}