fork download
  1. #include <bits/stdc++.h>
  2. #define INF 999999999
  3. #define N 2000
  4. #define mkp(a,b) make_pair(a,b)
  5. #define sz(c) (int)(c).size()
  6. using namespace std;
  7. int h , w , ch , cw , dh , dw , dp[N][N] , ans = INF;
  8. char a[N][N];
  9. int movex[] = {1 , 0 , -1 , 0};
  10. int movey[] = {0 , 1 , 0 , -1};
  11. queue < pair<int,int> > q;
  12. bool check(int x , int y){
  13. if(x < 0 || y < 0) return 0;
  14. if(x >= h || y >= w) return 0;
  15. return 1;
  16. }
  17. int main(){
  18. cin >> h >> w;
  19. cin >> ch >> cw;
  20. cin >> dh >> dw;
  21. dh--; dw--;
  22. ch--; cw--;
  23. for(int i = 0 ; i < h ; i++){
  24. for(int j = 0 ;j < w ; j++) cin >> a[i][j];
  25. }
  26. for(int i = 0 ; i < h ; i++){
  27. for(int j = 0 ; j < w ; j++){
  28. dp[i][j] =INF;
  29. }
  30. }
  31. dp[ch][cw] = 0;
  32. q.push(mkp(ch,cw));
  33.  
  34.  
  35. map<pair<int,int>,int> m;
  36.  
  37. while(sz(q) > 0){
  38. pair<int,int> p = q.front();
  39. int x = p.first , y = p.second;
  40. m[make_pair(x,y)]++;
  41.  
  42. q.pop();
  43. for(int i = x-2 ; i <= x + 2 ; i++){
  44. for(int j = y-2 ; j <= y+2 ; j++){
  45. if(!check(i,j)) continue;
  46. int d = abs(i-x) + abs(j-y) <= 1 ? 0 : 1;
  47. if(a[i][j]=='.' && dp[i][j]>dp[x][y]+d) {
  48. dp[i][j] = dp[x][y] + d;
  49. q.push(mkp(i,j));
  50. }
  51. }
  52. }
  53. }
  54.  
  55. for(auto z:m) {
  56. cout<<"("<<z.first.first<<","<<z.first.second<<") => seen " <<z.second<<" times"<<endl;
  57. }
  58.  
  59.  
  60. if(dp[dh][dw] == INF) cout <<"-1";
  61. else cout << dp[dh][dw] << '\n';
  62.  
  63. }
Success #stdin #stdout 0s 4540KB
stdin
8 13
1 1
1 13
.#.#.#.#.#.#.
.#.#.#.#.#.#.
.#.#.#.#.#.#.
.#.#.#.#.#.#.
.#.#.#.#.#.#.
.#.#.#.#.#.#.
.#.#.#.#.#.#.
.............
stdout
(0,0) => seen 1 times
(0,2) => seen 2 times
(0,4) => seen 3 times
(0,6) => seen 4 times
(0,8) => seen 5 times
(0,10) => seen 4 times
(0,12) => seen 5 times
(1,0) => seen 1 times
(1,2) => seen 2 times
(1,4) => seen 3 times
(1,6) => seen 4 times
(1,8) => seen 5 times
(1,10) => seen 5 times
(1,12) => seen 5 times
(2,0) => seen 2 times
(2,2) => seen 2 times
(2,4) => seen 3 times
(2,6) => seen 4 times
(2,8) => seen 4 times
(2,10) => seen 5 times
(2,12) => seen 4 times
(3,0) => seen 2 times
(3,2) => seen 2 times
(3,4) => seen 3 times
(3,6) => seen 4 times
(3,8) => seen 4 times
(3,10) => seen 4 times
(3,12) => seen 4 times
(4,0) => seen 2 times
(4,2) => seen 2 times
(4,4) => seen 3 times
(4,6) => seen 4 times
(4,8) => seen 4 times
(4,10) => seen 3 times
(4,12) => seen 4 times
(5,0) => seen 2 times
(5,2) => seen 2 times
(5,4) => seen 3 times
(5,6) => seen 3 times
(5,8) => seen 3 times
(5,10) => seen 3 times
(5,12) => seen 4 times
(6,0) => seen 2 times
(6,2) => seen 2 times
(6,4) => seen 3 times
(6,6) => seen 3 times
(6,8) => seen 3 times
(6,10) => seen 3 times
(6,12) => seen 4 times
(7,0) => seen 2 times
(7,1) => seen 2 times
(7,2) => seen 2 times
(7,3) => seen 3 times
(7,4) => seen 3 times
(7,5) => seen 3 times
(7,6) => seen 3 times
(7,7) => seen 3 times
(7,8) => seen 3 times
(7,9) => seen 3 times
(7,10) => seen 3 times
(7,11) => seen 3 times
(7,12) => seen 3 times
0