Facebook Hacker Cup: After the Dance Battle

Question

We want to find the shortest path between two points in a special grid. We can travel between adjacent squares in a single move, but we can also travel between cells of the same type (there are 10 types) in a single move no matter the distance between them.

How can we find the the number of steps required to travel between two points for a grid of up to 100x100 in size?

Answer 1

I solved this one during the contest by using BFS.

The problem can be modeled as a graph. Each cell is a node and has an edge with each adjacent cell. Instead of building the graph explicitly, we can simply keep the graph implicit by visiting each cell and its neighbours by computing grid coordinates as needed.

Each cell also has an edge to all cells of the same colour. We can add this to our graph by keeping lists of cells of each colour and visiting all cells of the same colour as the current cell.

Something like Dijkstra or A* would work (they are essentially a BFS with a priority queue/heuristic after all), but implementing that for such a simple problem would be serious overkill.

Code follows (in C++):

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <map> 

using namespace std;

char grid[101][101];
int cost[101][101];

vector<pair<int,int> > colour[10]; // lists of same coloured cells

//used to compute adjacent cells
int dr[]={ 0, 0, 1,-1};
int dc[]={ 1,-1, 0,0};

int rows,cols; // total rows and coloumns


int bfs(pair<int,int> start){
    memset(cost,-1,sizeof(cost)); // all unvisited nodes have negative cost to mark them
    cost[start.first][start.second]=0; // start node has cost 0

    queue<pair<int,int> > Q;
    Q.push(start);

    while (!Q.empty()){

        pair<int,int> node=Q.front();Q.pop();
        int r=node.first;
        int c=node.second;
        int cst=cost[r][c];
        if (grid[r][c]=='E'){
            return cst;
        }

        // search adjacent cells
        for(int i=0;i<4;i++){
            int nr=r+dr[i];
            int nc=c+dc[i];
            if (nr>=0 && nr<rows && nc>=0 && nc<cols && cost[nr][nc]<0 && grid[nr][nc]!='W'){
                cost[nr][nc]=cst+1;
                Q.push(make_pair(nr,nc));
            }
        }

        // search cells of the same colour
        if (grid[r][c]>='1' && grid[r][c]<='9'){
            vector<pair<int,int> > &trans=colour[grid[r][c]-'0'];
            for(int i=0;i<trans.size();i++){
                pair<int,int> next=trans[i];
                if (cost[next.first][next.second]<0){
                    cost[next.first][next.second]=cst+1;
                    Q.push(next);
                }
            }
        }
    }
    return -1;
}

int main(){
    int N;
    cin>>N;
    while(N--){
        cerr<<"cases left"<<N<<endl;
        cin>>rows>>cols;
        pair<int,int> start;
        for(int i=0;i<10;i++) colour[i].clear();

        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                cin>>grid[i][j];

                if (grid[i][j]=='S'){
                    start=make_pair(i,j);
                }
                else if (grid[i][j]>='1' && grid[i][j]<='9'){
                    colour[grid[i][j]-'0'].push_back(make_pair(i,j));
                }
            }
        }
        cout<<bfs(start)<<"\n";
    }

    return 0;
}