题目链接:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=388#problem/B

题意:求点数并按升序输出;

我的基本思路:BFS+DFS

code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 52
char map[MAX][MAX];
int visit[MAX][MAX],sum_dice,d_x[4]={-1,0,1,0},d_y[4]={0,1,0,-1};
int visit_dfs[MAX][MAX];//dfs的标记数组
int number[1000];
int m,n;
struct
{
int x;
int y;
}queu[40000];//队列
int bottom,pre;
int comp(const void *a,const void *b)//快速排序
{
return *((int*)a)-*((int*)b);
}
void dfs(int a,int b)//用来寻找和标记相连的X
{
int x,y,i;
if(map[a][b]==’X’&&visit_dfs[a][b]!=1)
{
visit_dfs[a][b]=1;

for(i=0;i<4;i++)//遍历相邻的四个方向
{
x=a+d_x[i];
y=b+d_y[i];
if((x>=0&&x<=m-1)&&(y>=0&&y<=n-1))
dfs(x,y);
}
}
}
int bfs_sum(int a,int b)//遍历一个骰子面并返回点数
{
int sum=0,x,y,i;
queu[pre].x=a;
queu[pre++].y=b;
if(map[a][b]==’X’&&visit_dfs[a][b]!=1)
{
dfs(a,b);
sum++;
}
while(bottom<pre)
{
for(i=0;i<4;i++)
{
x=queu[bottom].x+d_x[i];
y=queu[bottom].y+d_y[i];
if((x>=0&&x<=m-1)&&(y>=0&&y<=n-1)&&map[x][y]==’X’&&visit_dfs[x][y]!=1)
{
dfs(x,y);
sum++;
}
if((x>=0&&x<=m-1)&&(y>=0&&y<=n-1)&&(map[x][y]!=’.’&&visit[x][y]!=1))
{
queu[pre].x=x;
queu[pre++].y=y;
visit[x][y]=1;
}
}
bottom++;
}
return sum;
}
int check()//依次查找面数
{
int i,j,k=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(map[i][j]!=’.’&&visit[i][j]!=1)
number[k++]=bfs_sum(i,j);
return k;
}
int main()
{
int t=0,i;
while(scanf(“%d%d”,&n,&m),m||n)
{
t++;
bottom=pre=0;
memset(map,0,sizeof(map));
memset(visit,0,sizeof(visit));
memset(visit_dfs,0,sizeof(visit_dfs));
getchar();
for(i=0;i<m;i++)
gets(map[i]);

printf(“Throw %d\n”,t);

sum_dice=check();

qsort(number,sum_dice,sizeof(int),comp);
for(i=0;i<sum_dice;i++)
{
if(i==0)
printf(“%d”,number[i]);
else
printf(” %d”,number[i]);
}
printf(“\n\n”);
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation