Codeforce 1182B Plus from Picture
题目链接:http://codeforces.com/problemset/problem/1182/B
题意:检查图中 * 形成的是否是唯一的十字。
思路:dfs找到十字的中心,反向消除十字,最后检查是否有余留的 * ,如果有则图案不正确输出NO。
AC代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m; 4 char mp[505][505]; 5 int dx[4] = {0,1,0,-1}; 6 int dy[4] = {-1,0,1,0}; 7 bool check(int x,int y) 8 { 9 if(mp[x][y] != '*')return false; 10 if(mp[x + 1][y] != '*')return false; 11 if(mp[x - 1][y] != '*')return false; 12 if(mp[x][y + 1] != '*')return false; 13 if(mp[x][y - 1] != '*')return false; 14 return true; 15 } 16 void up(int x,int y) 17 { 18 while(mp[x][++y] == '*') mp[x][y] = '.'; 19 } 20 void down(int x,int y) 21 { 22 while(mp[x][--y] == '*') mp[x][y] = '.'; 23 } 24 void left(int x,int y) 25 { 26 while(mp[--x][y] == '*') mp[x][y] = '.'; 27 } 28 void right(int x,int y) 29 { 30 while(mp[++x][y] == '*') mp[x][y] = '.'; 31 } 32 int main() 33 { 34 cin >> n >> m; 35 bool flag = false; 36 for(int i = 0;i < n;i++) 37 { 38 cin >> mp[i]; 39 } 40 for(int i = 0;i < n;i++) 41 { 42 for(int j = 0;j < m;j++) 43 { 44 if(check(i,j)) 45 { 46 mp[i][j] = '.'; 47 up(i,j); 48 down(i,j); 49 left(i,j); 50 right(i,j); 51 flag = true; 52 break; 53 } 54 } 55 if(flag)break; 56 } 57 for(int i = 0;i < n;i++) 58 { 59 for(int j = 0;j < m;j++) 60 { 61 if(mp[i][j] == '*') 62 { 63 flag = false; 64 break; 65 } 66 } 67 } 68 if(flag) cout << "YES"; 69 else cout << "NO"; 70 return 0; 71 } 72 /* 73 5 5 74 ..*.. 75 ..... 76 ..*.. 77 ***** 78 ..*.. 79 */