DEVJERRY - Editorial

PROBLEM LINK:

Contest
Practice

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:

\text{Answer} = \begin{cases} |s_x - e_x| + |s_y - e_y| + 2 & \text{if $B$ is directly in the middle of $S$ and $E$} \\ |s_x - e_x| + |s_y - e_y| & \text{otherwise} \end{cases}

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)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester 1
Tester 2

i used this manhattan approach… used following code
#include<stdio.h>
#include<stdlib.h>
int main()
{
int t,n,sx,sy,ex,ey,bx,by,min=0;
scanf("%d",&t);
while(t–)
{
scanf("%d%d%d%d%d%d%d",&n,&sx,&sy,&ex,&ey,&bx,&by);
min=sx-ex;
if(min<0)
min=-min;
if(sy-ey<0)
min+=ey-sy;
else
min+=sy-ey;
if((sx==ex && sx==bx) || (sy==ey && sy==by))
min+=2;
printf("%d\n",min);
}
return 0;
}
it gave wrong answer… can anybody point out mistake

1 Like

weak test data even http://www.codechef.com/viewsolution/7124382 this pass … which is wrong on even given sample tests.

3 Likes

why is this solution given WA

please can anyone tell the test cases for which it fails

i have not used any of the Breadth-first search or Manhattan distance

1 Like

please tell test case for which my solution is giving wrong answer.

@hkara657 your solution did not passed because you need to check if bomb,starting and ending cordinates are part of the same line then check if bomb is between the source and destination or not. This happened with me also. If bomb will be between source and destination then your code works but if bomb is after destination then answer will be either abs(sx-ex) or abs(sy-ey)

@ag0965 read my above comment or look at my solution it will surely help

http://www.codechef.com/viewsolution/7123566

Can someone please point out the errors in my code?

@ag0965 and @subham_pasari
Check for case:

1

3 2 3 2 2 2 1

Your code gives 3 but the answer is 1.
Spot the error yourself, happy debugging!

1 Like

@subham_pasari your code is also wrong in case all the three points in same line but bomb is after the destination. Check this test case

1

3 1 2 2 2 3 2 … This comment is meant for all people who are getting WA.Please check this test case it must be giving 3 in your code but correct answer is 1

@dpraveen Well in the contest the solution was accepted but today I saw my solution was wrong, but I use bfs may be there was some flaw in my code, but this is wrong you have weak test cases at the time of contest, I submitted my code it got accepted than I leave it I didn’t check bugs in my code due to your mistakes or something I don’t know… After 3 days It gets updated as wrong answer…So, this is judgement? This is not fair If there were strong cases I would have corrected my bugs. This is much disappointing for me…

1 Like

I just dont know what happened, I got the AC its my link of correct solution which was accepted and was AC.

http://www.codechef.com/viewsolution/7118489

But now it is showing WA … whats the matter with Codechef

@jain_mj codechef re judged your solution and it was found wrong. See this case

1

5 2 2 4 2 1 2

This is in the case when your starting coordinates are between the bomb ones and destination then your algorithm will fail. You can have a look at my


[1] 


  [1]: http://www.codechef.com/viewsolution/7119073

yahhh!!! even i used the same approach dont know what’s wrong in it!?