HackerRank: Coin on the Table

HackerRank: Coin on the Table
You have a rectangular board consisting of N rows, numbered from 1 to N, and M columns, numbered from 1 to M. The top left is (1,1) and the bottom right is (N,M). Initially - at time 0 - there is a coin on the top-left cell of your board. Each cell of your board contains one of these letters:

*: Exactly one of your cells has letter '*'.

U: If at time t, the coin is on the cell(i,j) and cell(i,j) has letter 'U', the coin will be on the cell(i-1,j) in time t+1, if i > 1. Otherwise there is no coin on your board at time t+1.

L: If at time t, the coin is on the cell(i,j) and cell(i,j) has letter 'L', the coin will be on the cell(i,j-1) in time t+1, if j > 1. Otherwise there is no coin on your board at time t+1.

D: If at time t, the coin is on the cell(i,j) and cell(i,j) has letter 'D', the coin will be on the cell(i+1,j) in time t+1, if i < N. Otherwise there is no coin on your board at time t+1.

R: If at time t, the coin is on the cell(i,j) and cell(i,j) has letter 'R', the coin will be on the cell(i,j+1) in time t+1, if j < M. Otherwise there is no coin on your board at time t+1.

When the coin reaches a cell that has letter '*', it will stay there permanently. When you punch on your board, your timer starts and the coin moves between cells. Before starting the game, you can make operations to change the board, such that, you are sure that at time K the coin will reach the cell having letter '*'. In each operation you can select a cell with some letter other than '*' and change the letter to 'U', 'L', 'R' or 'D'. You need to carry out as few operations as possible in order to achieve your goal. Your task is to find the minimum number of operations.

BFS:
  cost = new int[N][M];
  for (int i = 0; i < N; i++)
   // for (int j = 0; j < M; j++)
   Arrays.fill(cost[i], Integer.MAX_VALUE);

  int ret = bfs(k);
  if (ret == Integer.MAX_VALUE)
   ret = -1;

  System.out.println(ret);

 class Node implements Comparable<Node> {
 public int x;
 public int y;
 public int k;
 public int cost; }

 private int bfs(int K) {
  Queue<Node> queue = new PriorityQueue<Node>();
  queue.add(new Node(0, 0, K, 0));
  while (!queue.isEmpty()) {
   Node node = queue.poll();
   int x = node.x;
   int y = node.y;
   int k = node.k;
   int cost = node.cost;

   this.cost[x][y] = Math.min(this.cost[x][y], cost);
   if (board[x].charAt(y) == '*' && k >= 0)
    return this.cost[x][y];
   else if (k < 0)
    continue;

   for (int i = 0; i < 4; i++) {
    int xx = x + dx[i];
    int yy = y + dy[i];
    if (inBoard(xx, yy)) {
     int c = board[x].charAt(y) == ch[i] ? 0 : 1;
     if (c + cost < this.cost[xx][yy])
      queue.add(new Node(xx, yy, k - 1, c + cost));
    }
   }
  }
  return -1;
 }

 private boolean inBoard(int x, int y) {
  return x >= 0 && x < N && y >= 0 && y < M;
 }
}

DFS:
https://github.com/derekhh/HackerRank/blob/master/coin-on-the-table.cpp
http://fenghaolw.blogspot.com/2014/01/coin-on-table.html
char map[52][52];
int best[52][52][1001];
int n, m, k;

void update(int row, int col, int time, int val)
{
if (row < 0 || row >= n) return;
if (col < 0 || col >= m) return;
if (time > k) return;

if (val < best[row][col][time] || best[row][col][time] == -1)
{
best[row][col][time] = val;

if (map[row][col] != '*')
{
update(row, col + 1, time + 1, val + (map[row][col] != 'R'));
update(row, col - 1, time + 1, val + (map[row][col] != 'L'));
update(row - 1, col, time + 1, val + (map[row][col] != 'U'));
update(row + 1, col, time + 1, val + (map[row][col] != 'D'));
}
else
{
update(row, col, time + 1, val);
}
}
}

int main()
{
cin >> n >> m >> k;
int r, c;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
cin >> map[i][j];
if (map[i][j] == '*')
r = i, c = j;
}
memset(best, -1, sizeof(best));
update(0, 0, 0, 0);
cout << best[r][c][k] << endl;
return 0;
}

Time Complexity: O(NMK)

Required Knowledge: DP
Also check http://www.cnblogs.com/sunshineatnoon/p/3919423.html

A DP solution is not hard to come up with. Let `f(i,j,k)` denote the minimum # of letter replacement we have to make to arrive cell `(i,j)` starting from `(1,1)` at time `k`. Then, the recurrence simply looks like `

f(i,j,k)=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪0∞∞min⎛⎝⎜⎜⎜⎜f(i−1,j,k−1)+δ(i−1,j,i,j)f(i+1,j,k−1)+δ(i+1,j,i,j)f(i,j−1,k−1)+δ(i,j−1,i,j)f(i,j+1,k−1)+δ(i,j+1,i,j)⎞⎠⎟⎟⎟⎟if ‘i=1‘, ‘j=1‘ and ‘k=0‘if (‘i≠1‘ or ‘j≠1‘) and ‘k=0‘if ‘i<1‘, or ‘i>N‘, or ‘j<1‘, or ‘j>M‘if ‘k>0‘ ,

` where `δ(i,j,x,y)=0` if the letter in cell `(i,j)` is the right one that leads to cell `(x,y)`, and `δ(i,j,x,y)=1` otherwise. The answer to this problem is simply `

mini=0Kf(N,M,i).

` If that value is `∞` then just output `−1`. If you have some concerns about this expression, please read the following sentence carefully.

When the coin reaches a cell that has letter *, it will stay there permanently

So why it is correct? Seems like the DP approach above may potentially change the letter of some cell more than once. However, it is easy to observe that, for any cell `(i,j)`, it will only be visited at most once in any optimal solution; otherwise, a cycle will be formed, and removing that cycle will clearly result in a better solution. So, even though we may change some letter more than once for some state, this state will always be beaten or never used in the future, thus can never contribute to our final output.

public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        int n = cin.nextInt();
        int m = cin.nextInt();
        int K = cin.nextInt();
        int x = 0, y = 0;
        char a[][] = new char[n][];
        for (int i=0; i<n; i++) {
            a[i] = cin.next().toCharArray();
            for (int j=0; j<m; j++)
                if (a[i][j] == '*') {
                    x = i;
                    y = j;
                }
        }


        int f[][][] = new int[K + 1][n][m];
        int ans = 1 << 29;
        for (int k=0; k<=K; k++)
            for (int i=0; i<n; i++)
                for (int j=0; j<m; j++) 
                    if (k == 0) f[k][i][j] = i == 0 && j == 0 ? 0 : 1 << 29;
                    else {
                        int res = 1 << 29;
                        if (i > 0)     res = Math.min(res, f[k - 1][i - 1][j] + (a[i - 1][j] == 'D' ? 0 : 1));
                        if (i < n - 1) res = Math.min(res, f[k - 1][i + 1][j] + (a[i + 1][j] == 'U' ? 0 : 1));
                        if (j > 0)     res = Math.min(res, f[k - 1][i][j - 1] + (a[i][j - 1] == 'R' ? 0 : 1));
                        if (j < m - 1) res = Math.min(res, f[k - 1][i][j + 1] + (a[i][j + 1] == 'L' ? 0 : 1));

                        f[k][i][j] = res;
                    }

        for (int k=0; k<=K; k++)
            ans = Math.min(ans, f[k][x][y]);

        if (ans < (1 << 29)) System.out.println(ans);
        else System.out.println(-1);

        cin.close();
    }

https://codepair.hackerrank.com/paper/gI7bCSVm?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9