ACM第一天研究懂的AC代码——BFS问题解答—

代码参考网址：http://blog.csdn.net/slience_perseverance/article/details/6706354

试题分析：

本题是研究red and black的一个标题，实际上可以通过深度优先搜索的方式进行查找。前后左右的方格只要不是红色的就可以进行计数那么最后可以到达的个数会有多少呢？本人菜鸟一枚，确实解题有很大的困难，所以在参考别人的AC之后有很大的感触，这里先将代码粘贴出来后分析吧。

//关于BFS问题解答
//参考网址
//http://blog.csdn.net/slience_perseverance/article/details/6706354
//习题zoj2165
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

struct node
{
int x,y;
}q[400+10];
struct node P,N;
//直接自己定义了方向
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char str[25][25];
int flag[25][25];
int main()
{
int c,r,i,j,front,rear;
while(scanf("%d%d",&c,&r)!=EOF,c*c+r*r)
{
memset(flag,0,sizeof(flag));
for(i=0;i<r;i++)scanf("%s",str[i]);
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)

if(str[i][j]=='@')break;
if(str[i][j]=='@')break;
}
N.x = i;
N.y = j;

flag[i][j] = 1;
q[0] = N;
front = 0;
rear =1;

while(front<rear)
{
N = q[front++];
for(i = 0;i<4;i++)
{
int tx = N.x + dir[i][0];
int ty = N.y + dir[i][1];
if(tx>=0&&tx<r&&ty>=0&&ty<c&&flag[tx][ty]!=1&&str[tx][ty] == '.')
{
P.x =tx;
P.y =ty;
q[rear++] =P;
flag[tx][ty] = 1;
}
}
}
printf("%d\n",rear);
}
return 0;
}

巴特西

ACM第一天研究懂的AC代码——BFS问题解答——习题zoj2165

最新文章

热门文章