PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Kevin Atienza and Sergey Kulik
Editorialist: Kevin Atienza
PREREQUISITES:
Breadth-first search, Manhattan distance
PROBLEM:
Jerry the mouse is in an n\times n grid, is at the location S := (s_x,s_y). He wants to move to the location E := (e_x,e_y). However, there is a bomb placed at B := (b_x,b_y) and so he has to avoid going there.
A move by Jerry consists of going up, down, left or right one cell as long as he doesn’t go off the grid. What is the minimum number of moves Jerry needs?
QUICK EXPLANATION:
The answer is the Manhattan distance between S and E, but add 2 if S and E are aligned vertically or horizontally, and B is directly in the middle. In other words:
Where B is directly in the middle of S and E if and only if one the following things hold:
- s_x = b_x = e_x and \min(s_y,e_y) < b_y < \max(s_y,e_y)
- s_y = b_y = e_y and \min(s_x,e_x) < b_x < \max(s_x,e_x)
EXPLANATION:
We’ll describe two approaches.
Breadth-first search
One way to compute the answer without thinking that much is to simply perform a breadth-first search starting from S and ending in E, but avoiding the bomb location B. Here’s a pseudocode:
function solve(n, S, E, B):
Let dist[1..n][1..n] be a 2D array // this represents the shortest distance to all cells
Initialize dist[i][j] to infinity for all 1 <= i, j <= n
dist[S.x][S.y] = 0
queue = new empty queue
push S at the back of queue
while queue is not empty:
P = (pop the front of queue)
for each neighbor Q of P in the four cardinal directions:
if (1 <= Q.x, Q.y <= n // i.e. Q is within range
and dist[Q.x][Q.y] = infinity // i.e. not yet visited
and Q != B): // i.e. not the bomb
dist[Q.x][Q.y] = dist[P.x][P.y] + 1
if Q == E:
// found! return answer
return dist[Q.x][Q.y]
else:
push Q at the back of queue
and here’s a sample implementation in Python:
def solve(n, S, E, B):
dist = {S: 0}
queue = [S]
f = 0
while f < len(queue):
P = px, py = queue[f]
f += 1
for dx, dy in [(1,0), (0,1), (-1,0), (0,-1)]:
Q = qx, qy = px + dx, py + dy
if (1 <= qx <= n and 1 <= qy <= n
and Q not in dist
and Q != B):
dist[Q] = dist[P] + 1
if Q == E:
return dist[Q]
else:
queue.append(Q)
for cas in xrange(input()):
n, sx, sy, ex, ey, bx, by = map(int, raw_input().strip().split())
print solve(n, (sx, sy), (ex, ey), (bx, by))
and a sample implementation in C++:
#include <stdio.h>
#define inf 1111111111 // some really large number
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int dist[41][41];
int qx[2111];
int qy[2111];
int main() {
int z;
scanf("%d", &z);
while (z--) {
int n, sx, sy, ex, ey, bx, by;
scanf("%d%d%d%d%d%d%d", &n, &sx, &sy, &ex, &ey, &bx, &by);
sx--, sy--, ex--, ey--, bx--, by--; // adjust to zero-indexing
// mark everything as not visited...
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
dist[x][y] = inf;
}
}
dist[sx][sy] = 0; // ...except start
// perform BFS
int q = 1;
qx[0] = sx;
qy[0] = sy;
for (int f = 0; f < q; f++) {
int x = qx[f];
int y = qy[f];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (0 <= nx && nx < n && 0 <= ny && ny < n // check if in range.
&& dist[nx][ny] >= inf // check if not yet visited.
&& !(nx == bx && ny == by)) { // check if not the bomb.
dist[nx][ny] = dist[x][y] + 1;
if (nx == ex && ny == ey) {
// found!
printf("%d\n", dist[nx][ny]);
q = 0; // clear queue and exit BFS
break;
} else {
// add to queue
qx[q] = nx;
qy[q] = ny;
q++;
}
}
}
}
}
}
It’s easy to see why this solution is correct, and since n is so small, this passes the time limit. The running time is O(n^2) because you have to visit every cell once.
Manhattan Distance
Let’s try to find a different solution by analyzing the problem a bit.
First, if there wasn’t a bomb, then the answer would be simple: just walk directly from S to E. But how many steps would that take? Well, you will have to take at least |s_x - e_x| steps horizontally and |s_y - e_y| steps vertically (because you have to be in the same row/column as E), so the answer is at least |s_x - e_x| + |s_y - e_y|. However, you can simply take |s_x - e_x| steps horizontally and |s_y - e_y| steps vertically in the right directions for a total of exactly |s_x - e_x| + |s_y - e_y| steps!
As a side note, the value |s_x - e_x| + |s_y - e_y| represents the Manhattan distance between S and E and has a variety of other uses. Let’s denote this quantity by D.
Now what if there’s a bomb? Note that the answer can still be D, especially if the bomb is out of the way from S to E. But what if the bomb blocks the way? Well, we can show that the answer is still D if we can find two disjoint paths of length D from S to E, like the following:
. . . . . . . . . . .
. . . . . . . . . . .
. . 1 1 1 1 1 E . . .
. . 1 . . . . 2 . . .
. . 1 . . . . 2 . . .
. . 1 . . . . 2 . . .
. . S 2 2 2 2 2 . . .
. . . . . . . . . . .
. . . . . . . . . . .
Assuming there are two such paths, say 1 and 2, why is the answer still D? This is because if the bomb is along path 1, then you can just take path 2 to go to E to avoid the bomb (because the paths are disjoint, you won’t encounter the bomb), and the same holds if the bomb is along path 2. If the bomb is in neither path, then you can take either!
Well, that’s great, but can we always find two such paths? Looking at the example above, we see that there are two such paths whenever S and E are not in the same row AND same column, i.e. s_x \not= e_x and s_y \not= e_y. But what if they are in the same row or column? Then there is exactly one path that takes D steps:
. . . . . . . . . . . . . .
. . . E . . . . . . . . . .
. . . 1 . . . . . . . . . .
. . . 1 . . . . S 1 1 1 E .
. . . 1 . . . . . . . . . .
. . . S . . . . . . . . . .
. . . . . . . . . . . . . .
All other paths take longer. So if the bomb is inside that path, then we have to take a detour:
. . . . . . . . . . . . . .
. . * E . . . . . . . . . .
. . * . . . . . * * * * * .
. . * B . . . . S . B . E .
. . * . . . . . . . . . . .
. . * S . . . . . . . . . .
. . . . . . . . . . . . . .
which takes two extra steps. But of course, if the bomb is not that path, the answer is still D.
How do we know if B is in that path? Well, it’s easy. B is in that path if and only if any of the following holds:
- s_x = b_x = e_x and \min(s_y,e_y) < b_y < \max(s_y,e_y) (aligned horizontally and the bomb is in the middle)
- s_y = b_y = e_y and \min(s_x,e_x) < b_x < \max(s_x,e_x) (aligned vertically and the bomb is in the middle)
Alternatively, B is in that path if and only if all of the following holds:
- s_x = e_x or s_y = e_y (start and end are aligned)
- \min(s_x,e_x) \le b_x \le \max(s_x,e_x) (b_x is in the middle)
- \min(s_y,e_y) \le b_y \le \max(s_y,e_y) (b_y is in the middle)
Thus, we now have the complete answer: it’s simply D + 2 if the above holds, and D otherwise!
Here’s a Python implementation:
for cas in xrange(input()):
n, sx, sy, ex, ey, bx, by = map(int, raw_input().strip().split())
print abs(sx - ex) + abs(sy - ey) + 2 * ((sx == ex or sy == ey)
and min(sx, ex) <= bx <= max(sx, ex)
and min(sy, ey) <= by <= max(sy, ey)
)
Now, what is the advantage of this solution? Notice that we only did a constant amount of computation, i.e. the running time is O(1). The size of n doesn’t matter: the amount of computation is still the same, regardless of n. Therefore, if the limit of n is increased from n \le 20 to, say, n \le 10^{18}, then this solution would still be efficient; however, the BFS solution runs slower for larger n, so for n = 10^{18} it could take around 10^{36} steps to finish, and even if we had a megacomputer which can process 10^{15} operations in a millisecond, it would still take at least 31 million millennia (or 31 billion years) to finish. Therefore, it pays to learn algorithms! (Unless you’re willing to wait 31 billion years of course)
Time Complexity:
O(1)