Problem Statement
The game is played on an R x C board; rows are numbered 0 to R - 1 from top to bottom and columns are numbered 0 to C - 1 from left to right. The cell in row r and column c is said to have coordinates (r, c). Each cell of the board either contains a single-digit number (0 to 9) or is empty. The board is given as String[] board where the j-th character of the i-th element represents the cell at row i and column j; this element is a digit character (‘0’ - ‘9’) if the cell contains the respective single-digit number or ‘.’ if the cell is empty. The goal of the game is to get from cell (r1, c1) to cell (r2, c2) with the fewest number of moves. A move is a jump of length d in a horizontal or vertical direction from a cell with a number d; more formally, if Arthur’s position is (r, c) and the cell contains a number d, he can move to cell (r - d, c), (r + d, c), (r, c - d), or (r, c + d). Note that an empty cell or a cell with number 0 is a dead-end. Arthur is also not allowed to leave the board at any time.
Tutorial
The problem statement is clean and definite. It requires computing single source shortest path with added constraints. The simple solution is to brute force all possible ways to reach (r2, c2). We could use BFS and find the minimum steps to enter the cell (r2, c2). But while computing the shortest path, we also need to find the appropriate value for a cell that contains ‘.’. In that sense, say the shortest path uses X ‘.’ cells, so we have X * 10 possibilities. This concludes simple BFS traversal doesn’t work. We need to store the cost that incurred for triplet (X, Y, D) where X & Y denotes the position in that grid and D indicates the digit used for that cell. \(f(X, Y, D) = min(f(X - D, Y - D, D') + 1), \{x | x\in\Bbb [0-9] \}\).
Code
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
public class NumberLabyrinthDiv2 {
int INF = 1000000000;
int[][][] dp = new int[55][55][55];
int n, m;
int[] dx = {0, 1, -1, 0};
int[] dy = {1, 0, 0, -1};
public int getMinimumNumberOfMoves(String[] board, int r1, int c1, int r2, int c2, int K) {
n = board.length;
m = board[0].length();
init();
final Queue<Integer> Q = new LinkedList<>();
Q.offer(r1);
Q.offer(c1);
Q.offer(K);
dp[r1][c1][K] = 0;
while(!Q.isEmpty())
{
int x, y, k, val;
x = Q.poll();
y = Q.poll();
k = Q.poll();
val = convert(board[x].charAt(y));
if(x == r2 && y == c2)
return dp[x][y][k];
for(int i = 1 ; i <= 9 ; i ++ )
{
if(( k > 0 && val == 10 ) || val == i)
{
for(int j = 0 ; j < 4 ;j ++)
{
int tx = x + dx[j] * i ;
int ty = y + dy[j] * i;
int tk = k - ((val == 10) ? 1 : 0);
if(isValid(tx, ty) && dp[tx][ty][tk] > dp[x][y][k] + 1)
{
dp[tx][ty][tk] = dp[x][y][k] + 1;
Q.offer(tx);
Q.offer(ty);
Q.offer(tk);
}
}
}
}
}
return -1;
}
private boolean isValid(int tx, int ty) {
return (tx >= 0 && tx < n && ty >=0 && ty < m);
}
private Integer convert(char c) {
if(c >= '0' && c <= '9')
return c - '0';
return 10;
}
private void init() {
for(int i = 0 ; i < 55 ; i++)
for(int j = 0 ;j < 55 ;j ++)
Arrays.fill(dp[i][j], INF);
}
}