題目連接：http://codeforces.com/contest/275/problem/B 用深搜寫的，對(duì)于每一個(gè)黑格子，分四個(gè)方向深搜，因?yàn)橛兴姆N情況，標(biāo)記數(shù)組也就有了四種狀態(tài)，即記錄起點(diǎn)從哪個(gè)方向開始出發(fā)的（這個(gè)還有記錄拐彎次數(shù)均為借鑒得來，不過好歹是又學(xué)會(huì)了新的處理方式）。 最近一直在復(fù)習(xí)準(zhǔn)備補(bǔ)考，表示腦殘手殘的buff又開始肆虐了，寫一個(gè)搜索竟然讓我樣例都過不去好幾次。。
  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
|