Facebook Hacker Cup: After the Dance Battle

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 开发者_Go百科100x100 in size?

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

Make 10 arrays, each one containing the cells of corresponding type. Now run Dijkstra (or BFS), but when you visit a cell of type i, add all cells of type i to the queue and clear the corresponding array. This way you don't have to visit every edge between cells of the same type and the complexity is O(n^2) instead of O(n^4)

You can represent the maze as a graph and solve it using BFS (it works for this case and is simpler than Dijkstra and A*).

In order to fill the edges you can do this:

for each row
   for each line
      if char == 'S' mark this point as start
      if char == 'E' mark this point as end
      if char != 'W' then
         create edges between this point and its adjacents (only if they exist and aren't a wall)
         if char >= '1' and char <= '9'
            create edges between this point and everyone with the same color

Then apply BFS (Breadth-first start) from start to end and you're done.

PS: In order to save memory, you should represent the graph using adjacency lists, since most of the nodes will have 4 neighbors.

I think the simplest way to solve is model the grid as a graph. Create an edge between 2 neighbors, also create one edge between two nodes of same type. After that, a simple BFS from source to dest can answer the shortest path between the two nodes.

http://en.wikipedia.org/wiki/Breadth-first_search

The complexity is O(V+E). V is the number of nodes, 100x100 and E is the number of edges

People here are mentioning Dijkstra. That solves, but it's desnecessary, since all edges cost one. Dijkstra is a special case of A-star algorithm, so A* is also too much for this problem.

Keep it simple, BFS!

This is a O(R*C) time and O(R*C) space solution:

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class DanceBattle {
    static final int INF = (int)(Integer.MAX_VALUE * 0.5);
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        for(int i = 0; i < N ; ++i) {
            int R = in.nextInt();
            int C = in.nextInt();
            int V = R*C;
            int node = 0, start = 0, end = 0;
            int nodeColor[] = new int[V];
            List<Integer>[] colorMap = new List[10];
            for(int color=0;color<10;++color)
                colorMap[color] = new LinkedList<Integer>();
            for(int r = 0; r < R; ++r) {
                String row = in.next();
                for(int c = 0; c<row.length(); ++c) {
                    char v = row.charAt(c);
                    if(v == 'S' ) start = node;
                    else if (v == 'E') end = node;
                    else if (v == 'W') nodeColor[node] = -1;
                    else {
                        int color = (int)(v - '0');
                        nodeColor[node] = color;
                        colorMap[color].add(node);
                    }
                    node++;
                }
            }
            int neighborhood4[][] = new int[V][4];
            for(int j =0 ; j< V; ++j) {
                int c = j % C;              
                int r = (j - c)/C;
                int grad = 0;
                if(neighbors(r,c,r,c+1, R, C))
                    neighborhood4[j][grad++] = (r) * C + (c+1);
                if(neighbors(r,c,r,c-1, R, C))
                    neighborhood4[j][grad++] = (r) * C + (c-1);
                if(neighbors(r,c,r+1,c, R, C))
                    neighborhood4[j][grad++] = (r+1) * C + (c);
                if(neighbors(r,c,r-1,c, R, C))
                    neighborhood4[j][grad++] = (r-1) * C + (c);
                if(grad < 4)
                    neighborhood4[j][grad] = -1;
            }

            //bfs
            int qbegin, qend;
            int[] Q = new int[V];
            int[] dist = new int[V];
            for(int j=0; j<V; j++) dist[j] = INF;
            dist[start] = 0;
            qbegin = qend = 0;
            Q[qend++] = start;
            int complexity = 0;
            while(qbegin != qend) {
                int currNode = Q[qbegin++];
                for(int j=0; j<4; j++) {
                    int neighbor = neighborhood4[currNode][j];
                    if(neighbor == -1) break;

                    int color = nodeColor[neighbor];
                    if(dist[neighbor] == INF && color != -1 ) {
                        Q[qend++] = neighbor;
                        dist[neighbor] = dist[currNode] + 1;
                    }
                    complexity++;                       
                }
                int color = nodeColor[currNode];
                if (color == 0)
                    continue;
                Iterator<Integer> iter = colorMap[color].iterator();
                while(iter.hasNext()) {
                    int viz = iter.next();
                    if(dist[viz] == INF) {
                        Q[qend++] = viz;
                        dist[viz] = dist[currNode] + 1;
                    }
                    iter.remove();
                    complexity++;                       
                }
            }
            System.out.printf("%d\n",dist[end]);
            //System.out.printf("(compl. %d V=%d constant: %.2f)\n", complexity, V, ((float)complexity) /  V);
        }
    }

    private static boolean neighbors(int ar, int ac, int br, int bc, int R, int C) {
        if(ar < 0 || ac < 0 || br < 0 || bc < 0) return false;
        if(ar >= R || ac >= C || br >= R || bc >= C) return false;
        return (Math.abs(ar - br) <= 1 && Math.abs(ac - bc) ==0) || (Math.abs(ar - br) == 0 && Math.abs(ac - bc) <=1);
    }
}

Construct a graph of all the squares as vertices with the edges marking possible moves and then let Dijkstra's algorithm work it out.

This could be done with Dynamic programming. Here you define connectivity, and start on the first square. You keep record of the minimal distance found to travel to a certain point. When you reached your endpoint, you find the path by backtracking the route of quickest descent.

In your case, you should define connections between adjacent cells, as well as between the cells of the same color.