Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2017
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. ll n,m,sr,sc,tr,tc;
  5. char arr[1005][1005];
  6. bool v[1005][1005];
  7.  
  8. int x[] = {0,0,1,-1};
  9. int y[] = {1 ,-1,0,0};
  10. //left 1
  11. //right 2
  12. //up 3
  13. //down 4
  14.  
  15.  
  16. bool isValid(int r,int c){
  17. return r >= 0 && r < n && c >= 0 && c < m;
  18. }
  19.  
  20. bool isChanged(int r,int c, int nr,int nc,int direct){
  21. if(nc == c+1 && direct == 2)
  22. return false;
  23. if(nr == r+1 && direct == 4)
  24. return false;
  25. if(nc == c-1 && direct == 1)
  26. return false;
  27. if(nr == r-1 && direct == 3)
  28. return false;
  29. return true;
  30. }
  31.  
  32. int getNewDirection(int r,int c,int nr, int nc){
  33. if(nc == c+1)
  34. return 2;
  35. if(nr == r+1)
  36. return 4;
  37. if(nc == c-1)
  38. return 1;
  39. if(nr == r-1)
  40. return 3;
  41. }
  42.  
  43.  
  44. void DFS(int r,int c,int turn,int direc){
  45. if(r == tr && c == tc){
  46. cout<<"YES";
  47. exit(0);
  48. }
  49. v[r][c] = true;
  50. int nr,nc;
  51. for(int i = 0 ; i < 4 ; ++i){
  52. nr = r + x[i];
  53. nc = c + y[i];
  54. if(!v[nr][nc] && isValid(nr,nc) && arr[nr][nc] != '*'){
  55. int newDir = direc;
  56. int neTurns = turn;
  57. if(isChanged(r,c,nr,nc,direc)){
  58. if(turn == 2){
  59. return ;
  60. }
  61. newDir = getNewDirection(r,c,nr,nc);
  62. neTurns++;
  63. }
  64. DFS(nr,nc,neTurns,newDir);
  65. }
  66. }
  67. }
  68.  
  69.  
  70.  
  71.  
  72. int main()
  73. {
  74. // freopen("omar.in","r",stdin);
  75. cin>>n>>m;
  76. for(int i = 0 ; i < n ; ++i){
  77. for(int j = 0 ; j < m ;++j){
  78. cin>>arr[i][j];
  79. if(arr[i][j] == 'S'){
  80. sr = i;
  81. sc = j;
  82. }else if(arr[i][j] == 'T'){
  83. tr = i ;
  84. tc = j;
  85. }
  86. }
  87. }
  88. DFS(sr,sc,0,1);
  89. memset(v,0,sizeof(v));
  90. DFS(sr,sc,0,2);
  91. memset(v,0,sizeof(v));
  92. DFS(sr,sc,0,3);
  93. memset(v,0,sizeof(v));
  94. DFS(sr,sc,0,4);
  95. cout<<"NO";
  96. return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement