Advertisement
Guest User

Untitled

a guest
Nov 23rd, 2017
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.85 KB | None | 0 0
  1. #include<iostream>
  2. #define N 200
  3. using namespace std ;
  4. int n , m , x_start , y_start , x_end , y_end , cont = 0 , x[20000] , y[20000] ;
  5. bool check = 1 , check_lo[N][N] ;
  6. class loc
  7. {
  8. public :
  9. bool can_walk , prev = false ;
  10. int dis = -1 ;
  11. };
  12. loc lo[N][N] ;
  13. loc lo_2[N][N] ;
  14. main ()
  15. {
  16. ios_base::sync_with_stdio(false);
  17. int count = 1 ;
  18. cin >> n >> m >> x_start >> y_start >> x_end >> y_end ;
  19. for ( int i = 1 ; i <= n ; i ++ )
  20. {
  21. for ( int j = 1 ; j <= m ; j ++ )
  22. {
  23. cin >> lo[i][j].can_walk ;
  24. lo_2[i][j].can_walk = lo[i][j].can_walk ;
  25. }
  26. }
  27. lo[x_start][y_start].prev = 1 ;
  28. lo[x_start][y_start].dis = 1 ;
  29. lo_2[x_end][y_end].prev = 1 ;
  30. lo_2[x_end][y_end].dis = 1 ;
  31. while ( check )
  32. {
  33. check = 0 ;
  34. for ( int i = 1 ; i <= n ; i ++ )
  35. {
  36. for ( int j = 1 ; j <= m ; j ++ )
  37. {
  38. if ( lo[i][j].prev == 1 )
  39. {
  40. check = 1 ;
  41. if ( ( lo[i+1][j].dis > lo[i][j].dis + 1 || lo[i+1][j].dis == -1 ) )
  42. {
  43. if ( lo[i+1][j].can_walk )
  44. {
  45. lo[i+1][j].dis = lo[i][j].dis + 1 ;
  46. lo[i+1][j].prev = 1 ;
  47. }
  48. else
  49. {
  50. lo[i+1][j].dis = -2 ;
  51. }
  52. }
  53. if ( ( lo[i-1][j].dis > lo[i][j].dis + 1 || lo[i-1][j].dis == -1 ) )
  54. {
  55. if ( lo[i-1][j].can_walk )
  56. {
  57. lo[i-1][j].dis = lo[i][j].dis + 1 ;
  58. lo[i-1][j].prev = 1 ;
  59. }
  60. else
  61. {
  62. lo[i-1][j].dis = -2 ;
  63. }
  64. }
  65. if ( ( lo[i][j+1].dis > lo[i][j].dis + 1 || lo[i][j+1].dis == -1 ) )
  66. {
  67. if ( lo[i][j+1].can_walk )
  68. {
  69. lo[i][j+1].dis = lo[i][j].dis + 1 ;
  70. lo[i][j+1].prev = 1 ;
  71. }
  72. else
  73. {
  74. lo[i][j+1].dis = -2 ;
  75. }
  76. }
  77. if ( ( lo[i][j-1].dis > lo[i][j].dis + 1 || lo[i][j-1].dis == -1 ) )
  78. {
  79. if ( lo[i][j-1].can_walk )
  80. {
  81. lo[i][j-1].dis = lo[i][j].dis + 1 ;
  82. lo[i][j-1].prev = 1 ;
  83. }
  84. else
  85. {
  86. lo[i][j-1].dis = -2 ;
  87. }
  88. }
  89. lo[i][j].prev = 0 ;
  90. }
  91. }
  92. }
  93. }
  94. check = 1 ;
  95. while ( check )
  96. {
  97. check = 0 ;
  98. for ( int i = 1 ; i <= n ; i ++ )
  99. {
  100. for ( int j = 1 ; j <= m ; j ++ )
  101. {
  102. if ( lo_2[i][j].prev == 1 )
  103. {
  104. check = 1 ;
  105. if ( ( lo_2[i+1][j].dis > lo_2[i][j].dis + 1 || lo_2[i+1][j].dis == -1 ) )
  106. {
  107. if ( lo_2[i+1][j].can_walk )
  108. {
  109. lo_2[i+1][j].dis = lo_2[i][j].dis + 1 ;
  110. lo_2[i+1][j].prev = 1 ;
  111. }
  112. else
  113. {
  114. lo_2[i+1][j].dis = -2 ;
  115. }
  116. }
  117. if ( ( lo_2[i-1][j].dis > lo_2[i][j].dis + 1 || lo_2[i-1][j].dis == -1 ) )
  118. {
  119. if ( lo_2[i-1][j].can_walk )
  120. {
  121. lo_2[i-1][j].dis = lo_2[i][j].dis + 1 ;
  122. lo_2[i-1][j].prev = 1 ;
  123. }
  124. else
  125. {
  126. lo_2[i-1][j].dis = -2 ;
  127. }
  128. }
  129. if ( ( lo_2[i][j+1].dis > lo_2[i][j].dis + 1 || lo_2[i][j+1].dis == -1 ) )
  130. {
  131. if ( lo_2[i][j+1].can_walk )
  132. {
  133. lo_2[i][j+1].dis = lo_2[i][j].dis + 1 ;
  134. lo_2[i][j+1].prev = 1 ;
  135. }
  136. else
  137. {
  138. lo_2[i][j+1].dis = -2 ;
  139. }
  140. }
  141. if ( ( lo_2[i][j-1].dis > lo_2[i][j].dis + 1 || lo_2[i][j-1].dis == -1 ) )
  142. {
  143. if ( lo_2[i][j-1].can_walk )
  144. {
  145. lo_2[i][j-1].dis = lo_2[i][j].dis + 1 ;
  146. lo_2[i][j-1].prev = 1 ;
  147. }
  148. else
  149. {
  150. lo_2[i][j-1].dis = -2 ;
  151. }
  152. }
  153. lo_2[i][j].prev = 0 ;
  154. }
  155. }
  156. }
  157. }
  158. for ( int i = 1 ; i <= n ; i ++ )
  159. {
  160. for ( int j = 1 ; j <= m ; j ++ )
  161. {
  162. if ( lo[i][j].dis == lo_2[i][j].dis && lo[i][j].dis == -2 )
  163. {
  164. x[cont] = i ;
  165. y[cont] = j ;
  166. cont ++ ;
  167.  
  168. }
  169. }
  170. }
  171. int min_1 = 999999 ;
  172. for ( int i = 0 ; i < cont ; i ++ )
  173. {
  174. for ( int a = -1 ; a <= 1 ; a += 2 )
  175. {
  176. for ( int b = -1 ; b <= 1 ; b += 2 )
  177. {
  178. if ( lo[ x[i] + a ][ y[i] ].dis > 0 && lo_2[ x[i] + b ][ y[i] ].dis > 0 )
  179. {
  180. if ( lo[ x[i] + a ][ y[i] ].dis + lo_2[ x[i] + b ][ y[i] ].dis < min_1 )
  181. {
  182. min_1 = lo[ x[i] + a ][ y[i] ].dis + lo_2[ x[i] + b ][ y[i] ].dis ;
  183. }
  184. }
  185. if ( lo[ x[i] + a ][ y[i] ].dis > 0 && lo_2[ x[i] ][ y[i] + b ].dis > 0 )
  186. {
  187. if ( lo[ x[i] + a ][ y[i] ].dis + lo_2[ x[i] ][ y[i] + b ].dis < min_1 )
  188. {
  189. min_1 = lo[ x[i] + a ][ y[i] ].dis + lo_2[ x[i] ][ y[i] + b ].dis ;
  190. }
  191. }
  192. if ( lo[ x[i] ][ y[i] + a ].dis > 0 && lo_2[ x[i] + b ][ y[i] ].dis > 0 )
  193. {
  194. if ( lo[ x[i] ][ y[i] + a ].dis + lo_2[ x[i] + b ][ y[i] ].dis < min_1 )
  195. {
  196. min_1 = lo[ x[i] ][ y[i] + a ].dis + lo_2[ x[i] + b ][ y[i] ].dis ;
  197. }
  198. }
  199. if ( lo[ x[i] ][ y[i] + a ].dis > 0 && lo_2[ x[i] ][ y[i] + b ].dis > 0 )
  200. {
  201. if ( lo[ x[i] ][ y[i] + a ].dis + lo_2[ x[i] ][ y[i] + b ].dis < min_1 )
  202. {
  203. min_1 = lo[ x[i] ][ y[i] + a ].dis + lo_2[ x[i] ][ y[i] + b ].dis ;
  204. }
  205. }
  206. }
  207. }
  208. }
  209. cout << cont << endl << min_1 + 1 ;
  210. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement