HDU4414 Finding crosses

　　原题传送：http://acm.hdu.edu.cn/showproblem.php?pid=4414

　　暴力？

　　依次扫描图形，碰到"#"的时候判断是否符合“十”条件，是的话count++，并且把该“十”图形的"#"变为"o"；如果不符合，也把和最开始搜到的"#"相连的"#"全部换成"o"。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <queue>
 5 #include <vector>
 6 #define N 55
 7 using namespace std;
 8 
 9 typedef pair<int, int> pii;
10 
11 int n, cnt;
12 char g[N][N];
13 int dr[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
14 queue<pii> q;
15 
16 bool pushadj(int m, int j, int len)
17 {
18     int x;
19     for(x = 1; x <= len; x ++)
20     {
21         if(m - x >= 0 && j - 1 >= 0 && g[m - x][j - 1] == '#')
22             return false;
23         if(m - x >= 0 && j + 1 < n && g[m - x][j + 1] == '#')
24             return false;
25         if(m + x < n && j - 1 >= 0 && g[m + x][j - 1] == '#')
26             return false;
27         if(m + x < n && j + 1 < n && g[m + x][j + 1] == '#') 
28             return false;
29         if(m - 1 >= 0 && j - x >= 0 && g[m - 1][j - x] == '#')
30             return false;
31         if(m - 1 >= 0 && j + x < n && g[m - 1][j + x] == '#')
32             return false;
33         if(m + 1 < n && j - x >= 0 && g[m + 1][j - x] == '#')
34             return false;
35         if(m + 1 < n && j + x < n && g[m + 1][j + x] == '#')
36             return false;
37     }
38     return true;
39 }
40 
41 bool fit(int i, int j)
42 {
43     int p = i, m, k1, k2;
44     bool flag = false;
45     q.push(make_pair(i, j));
46     while(p < n && g[p][j] == '#')
47         p ++;
48     if((p - i) >= 3 && (p - i) % 2 == 1)
49     {
50         m = (i + p) >> 1;
51         for(k1 = 1; j - k1 >= 0 && g[m][j - k1] == '#'; k1 ++);
52         for(k2 = 1; j + k2 < n && g[m][j + k2] == '#'; k2 ++);
53         k1--, k2--;
54         if(k1 + k2 + 1 == (p - i) && k1 == k2)
55             flag = pushadj(m, j, k1);  
56     }
57     while(!q.empty())
58     {
59         pii cur = q.front();
60         q.pop();
61         int x = cur.first;
62         int y = cur.second;
63         g[x][y] = 'o';
64         for(int t = 0; t < 4; t ++)
65         {
66             int cx = x + dr[t][0];
67             int cy = y + dr[t][1];
68             if(cx >= 0 && cx < n && cy >= 0 && cy < n && g[cx][cy] == '#')
69                 q.push(make_pair(cx, cy));
70         }
71     }
72     return flag;
73 }
74 
75 void bfs()
76 {
77     int i, j;
78     for(i = 0; i < n; i ++)
79         for(j = 0; j < n; j ++)
80             if(g[i][j] == '#' && fit(i, j))
81                     cnt ++;
82 }
83 
84 int main()
85 {
86     int i;
87     while(scanf("%d", &n), n)
88     {
89         memset(g, '\0', sizeof g);
90         for(i = 0; i < n; i ++)
91             scanf("%s", g[i]);
92         cnt = 0;
93         bfs();
94         printf("%d\n", cnt);
95     }
96     return 0;
97 }