Advertisement
Guest User

shortestPath

a guest
Apr 27th, 2017
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.33 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int yiha,n,m,step[100][100],minim=100000,x,y,p,q;
  5. char a[100][100];
  6.  
  7. int cari(int r,int s)
  8. {
  9. a[r][s]='#';
  10. if(a[r][s+1]!='#')
  11. {
  12. step[r][s+1]=step[r][s]+1;
  13. if(r==x && s+1==y)
  14. {
  15. minim=min(step[r][s+1],minim);
  16. a[r][s+1]='x';
  17. yiha=1;
  18. goto sini;
  19. }
  20. cari(r,s+1);
  21. }
  22. if(a[r+1][s]!='#')
  23. {
  24. step[r+1][s]=step[r][s]+1;
  25. if(r+1==x && s==y)
  26. {
  27. minim=min(step[r+1][s],minim);
  28. a[r+1][s]='x';
  29. yiha=1;
  30. goto sini;
  31. }
  32. cari(r+1,s);
  33. }
  34. if(a[r][s-1]!='#')
  35. {
  36. step[r][s-1]=step[r][s]+1;
  37. if(r==x && s-1==y)
  38. {
  39. minim=min(step[r][s-1],minim);
  40. a[r][s-1]='x';
  41. yiha=1;
  42. goto sini;
  43. }
  44. cari(r,s-1);
  45. }
  46. if(a[r-1][s]!='#')
  47. {
  48. step[r-1][s]=step[r][s]+1;
  49. if(r-1==x && s==y)
  50. {
  51. minim=min(step[r-1][s],minim);
  52. a[r-1][s]='x';
  53. yiha=1;
  54. goto sini;
  55. }
  56. cari(r-1,s);
  57. }
  58. sini:;
  59. if(yiha) a[r][s]='x';
  60. else
  61. a[r][s]=' ';
  62. step[r][s]=0;
  63. }
  64. int main()
  65. {
  66. scanf("%d %d",&n,&m);
  67. for(int i=1;i<=n;i++)
  68. {
  69. getchar();
  70. for(int j=1;j<=m;j++)
  71. scanf("%c",&a[i][j]);
  72. }
  73. // printf("%s\n", a[0]);
  74. scanf("%d %d",&p,&q);
  75. scanf("%d %d",&x,&y);
  76. step[p][q]=1;
  77. for(int i=1;i<=n;i++)
  78. printf("%s\n",a[i]+1);
  79. cari(p,q);
  80. printf("%d\n",minim-1);
  81. for(int i=1;i<=n;i++)
  82. printf("%s\n",a[i]+1);
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement