AC Again
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 306 Accepted Submission(s): 84
Description
“AC”这个单词大概是我们 ACMers 最希望听到的回答了。不过如果把它写下来，你还能认识吗？
现在给你一幅由点阵构成的图，它代表 'A' 或 'C' 的一个字母。你的任务就是把它们识别出来。
注意：
1.笔划可能有粗有细，但是我们保证字符在外形上是肉眼可辨别的。
2.我们保证笔划是连贯的，即对于任意一个有笔划的点，在它周围八个点内有一点有笔划，这两点就是相连贯的。
3.'A','C'这两个字符可能会按90，180，270这样的角度旋转。
现在给你一幅由点阵构成的图，它代表 'A' 或 'C' 的一个字母。你的任务就是把它们识别出来。
注意：
1.笔划可能有粗有细，但是我们保证字符在外形上是肉眼可辨别的。
2.我们保证笔划是连贯的，即对于任意一个有笔划的点，在它周围八个点内有一点有笔划，这两点就是相连贯的。
3.'A','C'这两个字符可能会按90，180，270这样的角度旋转。
Input
本题目包含多组测试，每两组测试之间用一个或多个空行隔开。
对于每组数据，系统将给你一个肉眼可以辨别的图形表示一个字符'A' 或 'C'。
系统保证每个图形的大小在 50 * 50 一下。
输入数据只包含 ' '(空格)和'*'两种字符，其中'*'表示该点有笔划。
对于每组数据，系统将给你一个肉眼可以辨别的图形表示一个字符'A' 或 'C'。
系统保证每个图形的大小在 50 * 50 一下。
输入数据只包含 ' '(空格)和'*'两种字符，其中'*'表示该点有笔划。
Output
对于每组数据，根据图形，在一行内输出 A 或 C。
Sample Input
*
* *
*****
* *
******
*
*
* ******
Sample Output
A
C
做题的关键在于，不知道如何来结束输入，结束之后又不知道如何来判断是哪个之母；
我们可以观察一下，A字母中间是空的，而C不是，其实这就是一个差别啊，所以我们可以从这入手来解决这类问题；
用搜索的方法，来进行判断；
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 char s[55][55]; 6 void bfs(int x,int y) 7 { 8 if(x<=50 && y<=50 && x>=0 && y>=0 && s[x][y]=='#') 9 { 10 s[x][y]='*';//遇见#的话就开始进行深度搜索； 11 bfs(x+1,y);//同时把#变成*； 12 bfs(x-1,y);//但是A内部的没有变成*，依然是#，所以在下面用flag进行判断 13 bfs(x,y+1); 14 bfs(x,y-1); 15 } 16 } 17 int main() 18 { 19 int i,j,n,flag; 20 int k=0; 21 memset(s,'#',sizeof(s)); 22 while(gets(s[1]+1)) 23 { 24 if(s[1][1]==' ') continue;//判断结束输入； 25 k=2; 26 while( gets(s[k]+1) && (s[k++][1] != ' ')); 27 for(i=0;i<51;i++) 28 for(j=0;j<51;j++) 29 if(s[i][j]!='*')//如果不是*则赋值成#； 30 s[i][j]='#'; 31 bfs(0,0);//开始调用 32 flag =0; 33 for(i=1;i<=50 && !flag;i++) 34 { 35 for(j=1;j<=50;j++) 36 { 37 if(s[i][j]=='#')//如果到最后，依然存在#，则s是A 38 { 39 flag =1;break; 40 } 41 } 42 } 43 if(flag)cout<<"A "; 44 else cout<<"C "; 45 memset(s,'#',sizeof(s)); 46 } 47 return 0; 48 }