December 2005 Problem 'ni' Analysis

Conceptually, this is a problem about shortest paths. For each shrubbery, we need the shortest path from Bessie to the shrubbery and from the shrubbery to the Knights who say Ni. The shortest path in a maze can be found using a technique called breadth first search (BFS). Initially, the starting point is added to a queue. Then, while the queue is not empty, the front of the queue is removed and processed. Any neighbours of this point that can be used but haven't yet been visited are added to the back of the queue. Because a queue is first-come-first-serve, the points nearest the start are processed first. For each point, we also keep track of where it was reached from so that we can reconstruct the path.

An interesting feature of BFS is that it gives you the shortest distance to all other points, not just the target point of interest. We can exploit this to speed up the solution. Instead of finding the shortest path from each shrubbery to the Knights who say Ni, we can find the shortest path from the knights to all the shrubberies, and later just reverse the path.

Here is USA student Carl Goh's solution:

#include<stdio.h>
#include<string.h>

const int	dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};

#define H 1000
#define W 1000
#define INF H*W+1

long w,h,step[2][H][W];
char map[H][W];

void bfs(long x, long y, char id){
    long i,j,nx,ny,ns,hd,ed;
    short qx[H*W],qy[H*W];

    memset(step[id],0,sizeof(step[id]));
    step[id][x][y] = 1;
    qx[0] = x; qy[0] = y; hd = 0; ed = 1;
    while(hd < ed){
        ns = step[id][qx[hd]][qy[hd]] + 1;
        for(i=0; i<4; i++){
            nx = qx[hd] + dx[i];
            ny = qy[hd] + dy[i];
            if(nx<h && nx>=0 && ny<w && ny>=0 && !step[id][nx][ny] &&
                (map[nx][ny] == 0 || map[nx][ny] == 4)){
                step[id][nx][ny] = ns;
                qx[ed] = nx; qy[ed] = ny; ed ++;
            }
        }
        hd ++;
    }
}

int main() {
    FILE *fin = fopen("ni.in","r");
    FILE *fout = fopen("ni.out","w");
    long i,j,min;

    fscanf(fin,"%ld%ld",&w,&h);
    for(i=0; i<h; i++)
        for(j=0; j<w; j++)
            fscanf(fin,"%d",&map[i][j]);

    for(i=0; i<h; i++){
        for(j=0; j<w; j++)
            if(map[i][j] == 2){
                map[i][j] = 0;
                bfs(i,j,0);
                break;
        }
        if(j < w) break;
    }

    for(i=0; i<h; i++){
        for(j=0; j<w; j++)
            if(map[i][j] == 3){
                bfs(i,j,1);
                break;
        }
        if(j < w) break;
    }

    min = INF;
    for(i=0; i<h; i++)
        for(j=0; j<w; j++)
            if(map[i][j] == 4 && step[0][i][j] && step[1][i][j] &&
            step[0][i][j]+step[1][i][j]-2 < min)
                min = step[0][i][j] + step[1][i][j] - 2;

    fprintf(fout,"%ld\n",min);

    fclose(fin);
    fclose(fout);
    return(0);
}