# Problem

https://atcoder.jp/contests/abc007/tasks/abc007_3

# Input

$H W$
$sy sx$
$gy gx$
$c_{0,0} c_{0,1} ... c_{0,W-1}$
...
$c_{H-1,0} c_{H-1,1} ... c_{H-1,W-1}$ .

$H$ - The height of maze.
$W$ - The width of maze.
$sy sx$ - The coordinates of starting point.
$gy gx$ - The coordinates of goal point.

# Output

Report the shortest path to get to $(gx, gy)$ from $(sx, sy)$ .
You can go up, down, left or right.
You can go though . and can't go though #.

# Explanation

The phrase "The shortest path" reminds me Breadth first search.
The time complexity is $O(H W)$ as each point is visited only once.

To calculate each point's distance from the starting point, you can use dynamic programming technique.

# Time complexity

O(H W)

# Solution

C++

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define EPS 0.0000000001
#define fequals(a,b) (fabs((a) - (b)) < EPS)

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (const Vector2 v) const { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (const Vector2 v) const { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (const double k) const { return Vector2(x * k, y * k); }
  Vector2 operator / (const double k) const { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 const v) { return x * v.x + y * v.y; }
  double cross (Vector2 const v) { return x * v.y - y * v.x; }
  
  bool parallel(Vector2 &other) {
    return fequals(0, cross(other));
  }
  
  bool orthogonal(Vector2 &other) {
    return fequals(0, dot(other));
  }
  
  bool operator < (const Vector2 &v) {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) { 
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) { 
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}

#define MAX_N 50
#define INFTY 3000

Int H, W, sx, sy, gx, gy;
char c_;
vector<bool> M(MAX_N * MAX_N, true);
vector<Int> dist(MAX_N * MAX_N, INFTY);

void input() {
  cin >> H >> W >> sy >> sx >> gy >> gx;
  sx--, sy--, gx--, gy--;
  loop(h,0,H) {
    loop(w,0,W) {
      cin >> c_;
      if (c_ == '#') M[h*W + w] = false;
    }
  }
}

Int bfs(Int sx, Int sy) {
  queue<Vector2> Q;
  dist[sy*W + sx] = 0;
  Q.push(Vector2(sx, sy));

  while (Q.size()) {
    Vector2 u = Q.front(); Q.pop();
    loop(dx,-1,2) {
      loop(dy,-1,2) {
        if (dx != 0 && dy != 0) continue;
        Vector2 next = u + Vector2(dx, dy);
        if (next.x < 0 || next.x >= W || next.y < 0 || next.y >= H) continue;
        if (!M.at(next.y*W+next.x)) continue;
        if (dist.at(next.y*W + next.x) < INFTY) continue;
        dist[next.y*W+next.x] = dist[u.y*W+u.x] + 1;
        if (next.x == gx && next.y == gy) {
          return dist[next.y*W+next.x];
        }
        Q.push(next);
      }
    }
  }

  return INFTY;
}

void solve() {
  cout << bfs(sx, sy) << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}

Shun

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!

ABC007 C - 幅優先探索