atcoder

# # Problem

## # 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

#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;
} 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!