首页 > 代码库 > hdu 1728

hdu 1728

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <cmath>
  4. char map[110][110];
  5. bool sign[110][110];
  6. int s_x, s_y, e_x, e_y;
  7. bool flag;
  8. int turn_step;
  9. int dir[][2] = {0,-1, -1,0, 0,1, 1,0};
  10. int n, m;
  11. int x_num;
  12. char str[110];
  13. void dfs(int turn, int x, int y, int wan)
  14. {
  15. sign[x][y] = 1;
  16. if(x==e_x && y == e_y)
  17. {
  18. if(wan <= turn_step)
  19. flag = 1;
  20. return ;
  21. }
  22. else if(flag) return;
  23. else if(wan > turn_step) return;
  24. else if (wan == turn_step && x !=e_x && y != e_y)
  25. return ;
  26. int tp_x = x, tp_y = y;
  27. for(int i=0; i<4; i++)
  28. {
  29. tp_x = x + dir[i][0];
  30. tp_y = y + dir[i][1];
  31. if( !(tp_x >= n || tp_x<0 || tp_y>=m || tp_y<0 || map[tp_x][tp_y] == ‘*‘ || sign[tp_x][tp_y] == true) )
  32. {
  33. if( wan == turn_step && ((tp_x == e_x) || (tp_y == e_y)) )
  34. {
  35. if(turn != i) wan++;
  36. dfs(i, tp_x, tp_y, wan);
  37. sign[tp_x][tp_y] = 0;
  38. if(turn != i) wan--;
  39. }
  40. else if(wan <turn_step)
  41. {
  42. if(turn != i) wan++;
  43. dfs(i, tp_x, tp_y, wan);
  44. sign[tp_x][tp_y] = 0;
  45. if(turn != i) wan--;
  46. }
  47. }
  48. }
  49. return;
  50. }
  51. int i, j;
  52. int main()
  53. {
  54. //freopen("read.txt", "r", stdin);
  55. int T;
  56. scanf("%d", &T);
  57. while(T--)
  58. {
  59. //memset(map, ‘\0‘, sizeof(map) );
  60. //memset(sign, 0, sizeof(sign) );
  61. //x_num = 0;
  62. scanf("%d%d", &n, &m);
  63. for(i=0; i<n; i++)
  64. {
  65. scanf("%s", str);
  66. for(j=0; j<m; j++)
  67. {
  68. map[i][j] = str[j];
  69. }
  70. }
  71. scanf("%d%d%d%d%d", &turn_step, &s_y, &s_x, &e_y, &e_x);
  72. s_x--; s_y--; e_x--; e_y--;
  73. flag = 0;
  74. dfs(-1, s_x, s_y, -1);
  75. if(!flag) printf("no\n");
  76. else printf("yes\n");
  77. }
  78. return 0;
  79. }



来自为知笔记(Wiz)


附件列表

     

    hdu 1728