BitComet 旗下网站

转到日志
相关贴吧:
acm of zju

zju2165 广度优先搜索

楼主 发表于:2008-09-11 16:29:26 [回复]

/*Red and Black  广度优先搜索   简单题
2008-09-11 16:17:15 Accepted 2165 C++ 00:00.05 848K 天将降大任于我
先把w,h周围的行和列,即将w+1列,h+1行,0行,0列都置为'#',,不能过去,然后输入的存放在i=1~h,j=1~w中。
这样无须考虑边界的情况,               char,string类型的数据不要用scanf(),printf()输入输出,否则很麻烦
*/
#include<iostream>
using namespace std;
int d[4][2]={0,1,1,0,0,-1,-1,0},temp;    //定义为前后左右相邻的4点
const int N=20;
char a[N+1][N+1];bool b[N+1][N+1];  //b[][]用来标记该点是否走过了
int fun(int x,int y)
{  
 for(int i=0;i<=3;i++)
 {
  if(a[x+d[i][0]][y+d[i][1]]=='.'&&b[x+d[i][0]][y+d[i][1]]==0)
  {
   b[x+d[i][0]][y+d[i][1]]=1;
             temp++;
    fun(x+d[i][0],y+d[i][1]);
  }
 }
 return temp;
}
int main()
{
 int w,h,i,j,x,y;
 while(cin>>w>>h&&(w&&h))
 {   temp=0;memset(b,0,sizeof(b));
  for(i=0,j=0;j<=w+1;j++) a[i][j]='#';
  for(i=0,j=0;j<=h+1;j++) a[j][i]='#';
  for(i=h+1,j=0;j<=w+1;j++) a[i][j]='#';
  for(i=0,j=w+1;i<=h+1;i++) a[i][j]='#';
  for(i=1;i<=h;i++)
   for(j=1;j<=w;j++)
    cin>>a[i][j];
  for(i=1;i<=h;i++)
   for(j=1;j<=w;j++)
    if(a[i][j]=='@'){x=i,y=j;i=h+1;break;}
    fun(x,y);
  cout<<temp+1<<endl;
 }
 return 0;
}

心难泰,世风坏,旧时正气今何在?正义寡,人情薄,闻道虽多,茅塞不开。怪!怪!怪! 空等待,几多载,冲出重围人心快!暴雨打,狂风袭,任他折磨,此志难改。耐!耐!耐!

1楼 发表于:2008-09-11 16:43:38 [回复]


网友回复

  • 2008-09-11 17:00:09
  • 日月明(3982864)
  • 我欣赏你,朋友!在品味你别具一格的小屋的同时,我收获着快乐!

2楼 发表于:2008-09-11 16:43:46 [回复]


网友回复

  • 2008-09-11 17:00:26
  • 日月明(3982864)
  • 我欣赏你,朋友!在品味你别具一格的小屋的同时,我收获着快乐!

3楼 发表于:2008-09-11 16:43:53 [回复]


网友回复

  • 2008-09-11 17:00:48
  • 日月明(3982864)
  • 不懂...不懂...

  • 我欣赏你,朋友!在品味你别具一格的小屋的同时,我收获着快乐!

 

您现在还没有登录,请在登录后发贴