acwing 471. 棋盘 解题记录

  1 #include   2 #include   3 
  4 using namespace std;
  5 
  6 const int N = 110;
  7 vectorint>> qipan(N, vectorint>(N, 0));
  8 vectorint>> vis(N, vectorint>(N, 0));
  9 vectorint>> mydistance(N, vectorint>(N, 99999));
 10 
 11 int m, n;            // mm格子棋牌  n个有颜色的
 12 int ans = 99999;
 13 
 14 int xchange[4] = { -1,1,0,0 };
 15 int ychange[4] = { 0,0,-1,1 };
 16 
 17 int CheckXY(int x, int y)
 18 {
 19     if (x 1 || x > m || y 1 || y > m || vis[x][y] == 1)
 20         return 0;
 21 
 22     return 1;
 23 }
 24 
 25 
 26 void dfs(int x,int y, int isMagic,int cost)
 27 {
 28     if (x == m && y == m && cost  ans) {
 29         ans = cost;
 30         return;
 31     }
 32 
 33     if (cost >= mydistance[x][y]) {
 34         //剪枝 如果现在开销已经大于经过这里的开销 则不必继续下去 因为开销会更大
 35         return;
 36     }
 37 
 38     mydistance[x][y] = cost;
 39 
 40     //向四个边扩展
 41     for (int i = 0; i 4; i++) {
 42         int nx = x + xchange[i], ny = y + ychange[i];
 43         if (1 != CheckXY(nx, ny)) {
 44             continue;
 45         }
 46         vis[nx][ny] = 1;
 47 
 48         if (isMagic == 0) {
 49             //没施法情况
 50             if (qipan[x][y] == qipan[nx][ny]) {
 51                 dfs(nx, ny, 0, cost);
 52             }
 53             else if (qipan[x][y] != qipan[nx][ny] && qipan[nx][ny] == 0) {
 54                 qipan[nx][ny] = qipan[x][y];
 55                 dfs(nx, ny, 1, cost+2);
 56                 qipan[nx][ny] = 0;
 57             }
 58             else if (qipan[x][y] != qipan[nx][ny] && qipan[nx][ny] != 0) {
 59                 dfs(nx, ny, 0, cost + 1);
 60             }
 61         }
 62         else {
 63             //上轮施法
 64             if (qipan[nx][ny] == 0) {
 65                 //连续两个无色块 返回
 66             }
 67             else if (qipan[nx][ny] != 0  && qipan[nx][ny] == qipan[x][y]) {
 68                 dfs(nx, ny, 0, cost);
 69             }
 70             else if (qipan[nx][ny] != 0 && qipan[nx][ny] != qipan[x][y]) {
 71                 dfs(nx, ny, 0, cost+1);
 72             }
 73         }
 74         vis[nx][ny] = 0;
 75     }
 76 }
 77 
 78 
 79 void StartCal()
 80 {
 81     int x = 1; int y = 1;
 82     int cost = 0;
 83     vis[1][1] = 1;
 84     dfs(x, y,0,cost);
 85 }
 86 
 87 
 88 //1 一个颜色  2 另一个颜色   0 无色
 89 int main()
 90 {
 91     //std::cout 
 92     cin >> m >> n;
 93 
 94 
 95     while (n--) {
 96         int x, y, c;
 97         cin >> x >> y >> c;
 98         qipan[x][y] = c+1;
 99     }
100 
101     StartCal();
102 
103     if (ans != 99999)
104         cout  ans;
105     else
106         cout 1;
107 
108     return 0;
109 }