青铜莲花池标程(宽度优先搜索路径)

  1. #include<cstdlib>
  2. #include<cstdio>
  3. using namespace std;
  4. struct bron
  5. {
  6. int x,y,t;
  7. }Q[5000000];
  8. int map[50][50];
  9. int step[9][2];
  10. int s=0xfffffff;
  11. int m,n,m1,m2;
  12. int sx,sy,ex,ey;
  13. bool flag[31][31];
  14. void bfs()
  15. {
  16. int q=1;
  17. int h=0;
  18. Q[0].x=sx,Q[0].y=sy,Q[0].t=0;
  19. int tx,ty,tt;
  20. int nx,ny;
  21. while(h<q)
  22. {
  23. tx=Q[h].x,ty=Q[h].y,tt=Q[h].t;
  24. if(tx==ex&&ty==ey)
  25. {
  26. if(tt<s) s=tt;
  27. h++;
  28. continue;
  29. }
  30. if(tt>=s)
  31. {
  32. h++;
  33. continue;
  34. }
  35. if(!flag[tx][ty])
  36. {
  37. h++;
  38. continue;
  39. }
  40. flag[tx][ty]=false;
  41. for(int i=1;i<=8;i++)
  42. {
  43. nx=step[i][0]+tx;
  44. ny=step[i][1]+ty;
  45. if(nx>=1&&nx<=m&&ny>=1&&ny<=n&&flag[nx][ny])
  46. {
  47. if(map[nx][ny]!=0)
  48. {
  49. Q[q].x=nx;
  50. Q[q].y=ny;
  51. Q[q].t=tt+1;
  52. q++;
  53. }
  54. }
  55. }
  56. h++;
  57. }
  58. printf("%d\n",s);
  59. }
  60. int main()
  61. {
  62. freopen("bronlily.in","r",stdin);
  63. freopen("bronlily.out","w",stdout);
  64. scanf("%d%d%d%d",&m,&n,&m1,&m2);
  65. for(int i=1;i<=m;i++)
  66. {
  67. for(int j=1;j<=n;j++)
  68. {
  69. flag[i][j]=true;
  70. }
  71. }
  72. int temp;
  73. for(int i=1;i<=m;i++)
  74. {
  75. for(int j=1;j<=n;j++)
  76. {
  77. scanf("%d",&temp);
  78. if(temp==0||temp==2) map[i][j]=0;
  79. else map[i][j]=temp;
  80. if(map[i][j]==3)
  81. {
  82. sx=i;
  83. sy=j;
  84. continue;
  85. }
  86. if(map[i][j]==4)
  87. {
  88. ex=i;
  89. ey=j;
  90. continue;
  91. }
  92. }
  93. }
  94. step[1][0]=m1,step[1][1]=m2;
  95. step[2][0]=m1,step[2][1]=-m2;
  96. step[3][0]=-m1,step[3][1]=m2;
  97. step[4][0]=-m1,step[4][1]=-m2;
  98. step[5][0]=m2,step[5][1]=m1;
  99. step[6][0]=m2,step[6][1]=-m1;
  100. step[7][0]=-m2,step[7][1]=m1;
  101. step[8][0]=-m2,step[8][1]=-m1;
  102. bfs();
  103. return 0;
  104. }
最后修改: 2013年05月14日 星期二 17:12