搜索代码鉴赏:细胞

包括深搜和宽搜,示例中只调用了宽度优先搜索函数,你可以自己尝试调用一下深度优先搜索

  1. //{程序的声明部分
  2. #include<fstream>
  3. using namespace std;
  4. ifstream fin("cellnum.in");
  5. ofstream fout("cellnum.out");
  6. int Lx[101],Ly[101],N,M,K;
  7. int sum;// for all function
  8. int queue[10000][3],head,tail; //for BFS
  9. char r; //for main
  10. bool bo[101][101];//check for all function
  11. const int rx[5]={0,0,1,0,-1},ry[5]={0,1,0,-1,0};//for all function
  12. //}
  13.  
  14.  
  15. void dfs(int x,int y)
  16. { //深度优先搜索的代码
  17. int i;
  18. if (bo[x][y]==true)
  19. {
  20. bo[x][y]=false;
  21. for(i=1;i<=4;i++)
  22. {
  23. dfs(x+rx[i],y+ry[i]);
  24. }
  25. }
  26. }
  27.  
  28.  
  29.  
  30.  
  31.  
  32. void bfs(int x,int y)
  33. { //宽度优先搜索的代码
  34. int i,Ix,Iy;
  35. head=1;tail=1;queue[1][1]=x;queue[1][2]=y;bo[x][y]=false;
  36. for(;head<=tail;)
  37. {
  38. for(i=1;i<=4;i++)
  39. {
  40. Ix=queue[head][1]+rx[i];Iy=queue[head][2]+ry[i];
  41. if (bo[Ix][Iy])
  42. {
  43. tail++;
  44. queue[tail][1]=Ix;queue[tail][2]=Iy;
  45. bo[Ix][Iy]=false;
  46. }
  47. }
  48. head++;
  49. }
  50. }
  51.  
  52.  
  53.  
  54.  
  55. int main()
  56. { //主函数!
  57. int i,j;
  58. fin>>N>>M;
  59. for(i=1;i<=N;i++)
  60. for(j=1;j<=M;j++)
  61. {
  62. fin>>r;
  63. if (r!='0')
  64. bo[i][j]=true;
  65. }
  66. for(i=1;i<=N;i++)
  67. for (j=1;j<=M;j++)
  68. if (bo[i][j]==true)
  69. {
  70. sum++;
  71. bfs(i,j);
  72. }
  73. fout<<sum<<endl;
  74. fin.close();
  75. fout.close();
  76. return 0;
  77. }
最后修改: 2013年05月1日 星期三 11:31