2154 - 发如雪
时间限制 : 3 秒
内存限制 : 128 MB
极冻之地，雪域有女，声媚，肤白，眸似月，其发如雪；有诗叹曰：千古冬蝶，万世凄绝。
——方文山《发如雪》歌词注解
即使没有玩过游戏，没有看过电视剧，你也应该听说过《轩辕剑》系列。它曾经和《仙剑奇侠传》一起，共同扛起了国产单机游戏的大旗。
《轩辕剑》系列塑造了许多有血有肉的人物：陈靖仇、于小雪、宇文拓……于小雪作为《轩辕剑》中的女主角，白发蓝眸，娇巧可爱，善良大方，温柔体贴。她从小生活在月河村，15岁时遇上生命中最重要的人—陈靖仇，从此开始了改变自己命运的传奇之旅。在此期间，她所展现的完美中国古代女子形象与其令人悲婉慨叹的人生抉择将一个外柔内刚的少女面对感情责任的重重挑战战胜自我，勇往直前的生命历程演义得淋漓尽致。
作为一款<span>RPG</span><span>游戏，轩辕剑中有很多智力谜题。其中一个就是给出一个迷雾遮住了一部分的地图，让你快速判断迷雾将地图分成了几块。</span>
题目输入
第一行为一个数字T，表示有T组输入数据（1<T<15）。
每组输入数据包含两个部分，第一行为地图的行数和列数（1<行数<15，1<列数<15）。接下来的m*n区域为具体的地图。其中”*”代表迷雾遮住的区域，“@”为地图中显示出来的区域。
题目输出
对于每组输入数据，输出“*”迷雾将地图分成了几块。我们规定只要“@”连着，无论横着竖着斜着都算一块。比如第二个例子3 5，@斜着能连接起来，即算迷雾完全没有分开@区域，算作1整块。
输入/输出样例
输入格式
4 1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@
输出格式
0 1 2 2
C语言解答
#include<stdio.h> #include<string.h> int n,m; char s[104][104]; int dir[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1}; int vis[104][104]; void dfs(int x,int y) { int i; if(x<0||x>=n||y<0||y>=m||vis[x][y]||s[x][y]=='*') return; vis[x][y]=1; for(i=0; i<8; i++) dfs(x+dir[i][0],y+dir[i][1]); } int main() { int i,j,ans,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(s,0,sizeof(s)); memset(vis,0,sizeof(vis)); ans=0; for(i=0;i<n;i++) scanf("%s",s[i]); for(i=0;i<n;i++) for(j=0;j<m;j++) if(s[i][j]=='@'&&!vis[i][j]) { ans++; dfs(i,j); } printf("%d\n",ans); } return 0; }
C++解答
#include <iostream> #include <cstring> #include <fstream> using namespace std; char mat[115][115]; int visited[115][115]; void dfs(int x,int y) { if((visited[x][y]==1 || mat[x][y]=='*' )) return; visited[x][y]=1; dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y+1); dfs(x,y-1); dfs(x,y+1); dfs(x+1,y-1); dfs(x+1,y); dfs(x+1,y+1); } int main() { //ifstream cin; //cin.open("5.in"); //ofstream cout; //cout.open("5.out"); int length,height; int testcase; cin>>testcase; while(testcase--) { cin>>length>>height; memset(mat,'*',sizeof(mat)); memset(visited,0,sizeof(visited)); int count=0; for(int i=1;i<=length;i++) { for(int j=1;j<=height;j++) { cin>>mat[i][j]; } } for(int i=1;i<=length;i++) { for(int j=1;j<=height;j++) { if(mat[i][j]=='@' && visited[i][j]==0) { dfs(i,j); count++; } } } cout<<count<<endl; } return 0; }