codeforces B. Convex Shape 解题报告

题目链接：http://codeforces.com/problemset/problem/275/B

题目内容：给出一个n * m 大小的grid，上面只有 black 和 white 两种颜色填充。问任意两个black cell 的连通是否满足最多转一次弯而达到。当然，如果有好多堆black cell 也是不满足条件的，即只能有一堆！！

这是继color the fence 之后，又一条花了我很长时间才做出来的题目，因为搜索这些技巧学不好，于是只能结合观察能力做出来了。其实最直接的方法应该是bfs，可惜= =，好啦我会加油的！！！

主要分成两个个部分判断：1、black cell 是否有且仅为一堆

2、判断是否存在这两种类型：

‘Z’ 类型比较难判断，借鉴了别人的思路：就是判断红色标识的两处地方是否都为'W'

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring>
  5 using namespace std;
  6 
  7 const int maxn = 50 + 5;
  8 char grid[maxn][maxn], tmp[maxn][maxn];
  9 int n, m, cnt;
 10 
 11 #define REP(i, n) for(i = 1; i <= (n); i++)
 12 
 13 void dfs(int x, int y)  // 判断是否为一堆black cell
 14 {
 15     if (x >= 1 && x <= n && y >= 1 && y <= m && tmp[x][y] == 'B')
 16     {
 17         tmp[x][y] = 'W';
 18         dfs(x-1, y);
 19         dfs(x+1, y);
 20         dfs(x, y-1);
 21         dfs(x, y+1);
 22     }
 23 }
 24 
 25 int main()
 26 {
 27     int i, j, l, k;
 28     while (scanf("%d%d", &n, &m) != EOF)
 29     {
 30         memset(grid, 0, sizeof(grid));
 31         memset(tmp, 0, sizeof(tmp));
 32         REP(i, n) REP(j, m)
 33         {
 34             cin >> grid[i][j];
 35             tmp[i][j] = grid[i][j];
 36         }
 37         cnt = 0;
 38            REP(i, n) REP(j, m)
 39         {       
 40             if (tmp[i][j] == 'B')
 41             {
 42                 dfs(i, j);
 43                 cnt++;
 44              }
 45         }
 46         if (cnt >= 2)     // 多于1堆
 47             printf("NO
");
 48         else
 49         {
 50             int flag = 0;
 51             // 判断类型1
 52             for (i = 1; i <= n && !flag; i++)
 53             {
 54                 for (j = 1; j <= m && !flag; j++)
 55                 {
 56                     if (grid[i][j] == 'B' && grid[i][j+1] == 'W')
 57                     {
 58                         j++;
 59                         while (grid[i][j] == 'W' && j <= m)
 60                             j++;
 61                         if (grid[i][j] == 'B' && j <= m)
 62                             flag = 1;
 63                     }
 64                 }
 65             }
 66             if (!flag)
 67             {
 68                 for (j = 1; j <= n && !flag; j++)
 69                 {
 70                     for (i = 1; i <= m && !flag; i++)
 71                     {
 72                         if (grid[i][j] == 'B' && grid[i+1][j] == 'W')
 73                         {
 74                             i++;
 75                             while (grid[i][j] == 'W' && i <= n)
 76                                 i++;
 77                             if (grid[i][j] == 'B' && i <= n)
 78                                 flag = 1;
 79                         }
 80                     }
 81                 }  
 82             }
 83             // 判断类型2
 84             if (!flag)
 85             {
 86                 REP(i, n) REP(j, m) REP(k, n) REP(l, m)
 87                 {
 88                     if (grid[i][j] == 'B' && grid[k][l] == 'B' && grid[k][j] == 'W' && grid[i][l] == 'W')
 89                     {
 90                         flag = 1;
 91                         break;
 92                     }
 93                 }
 94             }
 95             if (!flag)
 96                 printf("YES
");
 97             else
 98                 printf("NO
");
 99         }
100     }
101     return 0;
102 }