Facebook Hacker Cup: after the dance battle

Question

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

How to find the number of steps required to move between two points for a grid up to 100x100?

Answer 1

Make 10 arrays, each of which contains cells of the corresponding type. Now start 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. Thus, you do not need to visit each edge between cells of the same type, and the complexity is O (n ^ 2) instead of O (n ^ 4)

Answer 2

I decided this during the contest 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 explicitly plotting the graph, we can simply keep the graph implicit by visiting each cell and its neighbors, calculating the grid coordinates as necessary.

Each cell also has an edge for all cells of the same color. We can add this to our chart by saving lists of cells of each color and visiting all cells of the same color as the current cell.

Something like Dijkstra or * will work (in essence, it is a BFS with priority queue / heuristic), but implementing this for such a simple problem will be a serious overload.

The following code (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; } 

Answer 3

I think the easiest way to solve this is to model the grid as a graphic. Create a face between two neighbors, also create one edge between two nodes of the same type. After that, a simple BFS from source to dest can respond to the shortest path between two nodes.

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

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

People here mention Dijkstra. This solves, but it is necessary, because all the edges stand alone. Dijkstra is a special case of the A-star algorithm, so A * is too much for this problem.

Keep it simple, BFS!

This time is O (R * C) and O (R * C):

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

Answer 4

You can present the labyrinth in the form of a graph and solve it using BFS (it works for this case and is easier than Dijkstra and A *).

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 ( beginning of the first line ) from start to end , and you're done.

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

Answer 5

Construct a graph of all squares in the form of vertices with edges denoting possible movements, and then enable the Dijkstra algorithm.

Answer 6

This can be done using Dynamic Programming . Here you define connectivity and start with the first square. You record the minimum distance that can be found at a specific point. When you reach the end point, you will find the path, returning the path of rapid descent.

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