【dfs+染色】【HDOJ】5652 India and China Origins

http://acm.hdu.edu.cn/showproblem.php?pid=5652

这个题也可以用二分+并查集做。。。等更新

中国和印度之间有一块分成棋盘的陆地，白色的是平地（用0表示），黑色的是山峰（用1表示），给出初始情况

之后给出n年，每年长出山峰的坐标

求最早在几年的时候中国和印度之间被完全阻隔，即没有从第一行到最后一行的通路。

最开始将之后N年的山峰都长出来

从上到下将空地染色为2，从下到上将空地染色为3

再从最后一年长出的山峰开始删除，每次删除之后将新出现的空地与周围的2或3进行染色

直到某一次删除山峰后它的周围既有2染色又有3颜色，或这个山峰染上2色后可以通到最后一行，或染上3色可以通到第一行，就找到结果了

如果每次都不能通路，输出0（最开始就是堵住的路）

如果最开始染2或3时就找到通路，输出-1（永远不会被堵住）

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 char Map[505][505];
  5 int T, n, m, q;
  6 int dirx[4] = {0, 1, 0, -1};
  7 int diry[4] = {1, 0, -1, 0};
  8 typedef struct point{
  9     int x, y;
 10 }point;
 11 point p[505*505];
 12 bool path;
 13 bool result;
 14 bool temp2, temp3;
 15 
 16 void dfs(int x, int y, int z){
 17     if(x < 0 || x >= n || y < 0 || y >= m) return;
 18     if(Map[x][y] != '0') return;
 19     Map[x][y] = '0'+z;
 20     if(z == 2 && x == n-1) path = true;
 21     if(z == 3 && x == 0) path = true;
 22     for(int i = 0; i < 4; i++){
 23         dfs(x+dirx[i], y+diry[i], z);
 24     }
 25 }
 26 
 27 void Begin1(){
 28     for(int j = 0; j < m; j++){
 29         if(Map[0][j] == '0'){
 30             dfs(0, j, 2);
 31         }
 32     }
 33 }
 34 
 35 void Begin2(){
 36     for(int j = 0; j < m; j++){
 37         if(Map[n-1][j] == '0'){
 38             dfs(n-1, j, 3);
 39         }
 40     }
 41 }
 42 
 43 int main(){
 44     scanf("%d", &T);
 45     while(T--){
 46         path = false;
 47         result = false;
 48         memset(Map, 0, sizeof(Map));
 49         memset(p, 0, sizeof(p));
 50         scanf("%d%d", &n, &m);
 51         for(int i = 0; i < n; i++){
 52             scanf("%s", Map[i]);
 53         }
 54         scanf("%d", &q);
 55         for(int i = 0; i < q; i++){
 56             scanf("%d%d", &p[i].x, &p[i].y);
 57             Map[ p[i].x ][ p[i].y ] = '1';
 58         }
 59         Begin1();
 60         if(path){
 61             printf("-1
");
 62             continue;
 63         }
 64         Begin2();
 65         if(path){
 66             printf("-1
");
 67             continue;
 68         }
 69         for(int i = q-1; i >= 0; i--){
 70             temp2=false, temp3=false;
 71             for(int j = 0; j < 4; j++){
 72                 if(Map[ p[i].x+dirx[j] ][ p[i].y+diry[j] ] == '2') temp2 = true;
 73                 if(Map[ p[i].x+dirx[j] ][ p[i].y+diry[j] ] == '3') temp3 = true;
 74             }
//这里避免一个问题就是1111 1101 周围没有染色，现在删掉山峰之后第一次开始染颜色3的情况，要特判一下
 75             if(!temp2 && !temp3){
 76                 for(int j = 0; j < 4; j++){
 77                     if(p[i].x+dirx[j] == -1) temp2 = true;
 78                     if(p[i].x+dirx[j] == n) temp3 = true;
 79                 }
 80             }
 81             if(temp2 && temp3){
 82                 printf("%d
", i+1);
 83                 result = true;
 84                 break;
 85             }
 86             else if(temp2){
 87                 Map[ p[i].x ][ p[i].y ] = '0';
 88                 dfs(p[i].x, p[i].y, 2);
 89                 if(path){
 90                     printf("%d
", i+1);
 91                     result = true;
 92                     break;
 93                 }
 94             }
 95             else if(temp3){
 96                 Map[ p[i].x ][ p[i].y ] = '0';
 97                 dfs(p[i].x, p[i].y, 3);
 98                 if(path){
 99                     printf("%d
", i+1);
100                     result = true;
101                     break;
102                 }
103             }
104             else{
105                 Map[ p[i].x ][ p[i].y ] = '0';
106             }
107         }
108         if(!result) printf("0
");
109     }
110 
111     return 0;
112 }