Submission #64544332

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 1e3+5;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int n, m;
char a[N][N];
int D[N][N];

bool bound(int x, int y){
  return x >= 1 && y >= 1 && x <= n && y <= m;
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      cin >> a[i][j];
    }
  }
  int u, v;
  cin >> u >> v;
  memset(D, 0x3f, sizeof(D));
  D[u][v] = 0;
  deque<pi> q;
  q.push_front({u, v});
  while(!q.empty()){
    int x = (q.front()).first, y = (q.front()).second;
    q.pop_front();
    for(int d = 0; d < 4; d++){
      int z = x+dx[d], t = y+dy[d];
      if(bound(z, t) && a[z][t] != '#'){
        if(D[z][t] > D[x][y]){
          D[z][t] = D[x][y];
          q.push_front({z, t});
        }
      }
    }
    for(int M = 1; M <= 2; M++){
      for(int d = 0; d < 4; d++){
        int z = x+dx[d]*M, t = y+dy[d]*M;
        if(bound(z, t)){
          if(D[z][t] > D[x][y] + 1){
            D[z][t] = D[x][y] + 1;
            q.push_back({z, t});
          }
        }
      }
    }
  }

  cin >> u >> v;
  cout << D[u][v];
  return 0;
}

Submission Info

Judge Result