题目连接：http://codeforces.com/contest/275/problem/B 用深搜写的，对于每一个黑格子，分四个方向深搜，因为有四种情况，标记数组也就有了四种状态，即记录起点从哪个方向开始出发的（这个还有记录拐弯次数均为借鉴得来，不过好歹是又学会了新的处理方式）。 最近一直在复习准备补考，表示脑残手残的buff又开始肆虐了，写一个搜索竟然让我样例都过不去好几次。。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 int map[55][55], n, m;
9 char s[55][55];
10 const int d[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
11 bool inMap(int x, int y){
12 return x >= 0 && x < n && y >= 0 && y < m;
13 }
14 void dfs(int x, int y, int dir, int chg, int state){
15 map[x][y] = state;
16 for (int i = 0; i < 4; i++){
17 int xx = x + d[i][0];
18 int yy = y + d[i][1];
19 if (!inMap(xx, yy) || s[xx][yy] == 'W' || map[xx][yy] == state) continue;
20 if (i != dir && chg == 0) dfs(xx, yy, i, chg + 1, state);
21 else if (i == dir) dfs(xx, yy, i, chg, state);
22 }
23 }
24 int main(){
25 cin >> n >> m;
26 for (int i = 0; i < n; i++) cin >> s[i];
27 for (int i = 0; i < n; i++)
28 for (int j = 0; j < m; j++){
29 if (s[i][j] == 'B'){
30 memset(map, 0, sizeof(map));
31 for (int k = 0; k < 4; k++) dfs(i, j, k, 0, k + 1);
32 for (int k = 0; k < n; k++)
33 for (int l = 0; l < m; l++)
34 if (s[k][l] == 'B' && map[k][l] == 0){
35 cout << "NO" << endl;
36 return 0;
37 }
38 }
39 }
40 cout << "YES" << endl;
41 return 0;
42
|