Coin on the Table Redux

作者 QIFAN 日期 2016-10-09
Coin on the Table Redux

有一个 N 行 M 列的长方形board,最左上方的点为 (1, 1), 右下角的点为 (N, M)。当t=0时,有一个硬币静静的躺在左上角。board上的每一个点有以下这些字母及含义:

  • L:若t时硬币在 (i, j)t+1时硬币在(i, j-1)。 若j < 1,则硬币将离开board
  • D:若t时硬币在 (i, j)t+1时硬币在(i+1, j)。 若i > N-1,则硬币将离开board
  • U:若t时硬币在 (i, j)t+1时硬币在(i, j+1)。 若i > M-1,则硬币将离开board
  • *: 若某个点是 *, 则硬币将被困在这个点不得动弹。

目标:找到需要改动的最少方块值,使得硬币能从最下面一行离开board。任何一个方块可以改成’R’, ‘L’或’D’。

返回:离开最后一行每一个方块需要的改变数。

举例

  • 输入:
    RD
    *L

  • 输出:
    1,1

  • 解释:
    2*2的board,硬币从(1,0)点离开的方式:将’R’和*改成’D’((0,0) --> (1,0) --> leave),或将*改为’D’((0,0) --> (0,1) --> (1,1) --> (1,0) --> leave),最小改动数为1;硬币从(1,1)离开的方式:将’L’改为’D’,最小改动数为1。

思路

我的思路将move分成了三部分,到达第一行的move,到达第二行到最后一行的move,及最后离开board的move。

首行:到达(0,0)的cost为0,(0,j)的cost为到达(0,j-1)的cost加上从(0,j-1)(0,j)的cost,所以若(0,j-1)的值为’R’,则cost(0,j)= cost(0,j-1)(不用改变),其他情况则为cost(0,j)= cost(0,j-1)(0,j)的值改为’R’。

中间:到达(i,j)的最小改动分别是从上方来,从左方来和从右方来路径的最小值,但是首先要先算从上方来的给这一行赋值,从左从右可以一起算。

最后:若最后一行的值为D,则离开cost为到达该点的cost,其他情况则是原有cost+1(将值改为’R’)。

Solution

int[] minimum_changes(char[][] board) {
if(board == null || board.length == 0) return null;
int N = board[0].length;
int[] result = new int[N];
result[0] = 0;
for (int i = 1; i < N; i++) {
result[i] = result[i-1] + (board[0][i-1] == 'R' ? 0 : 1);
}
for (int i = 1; i < board.length; i++) {
// from up
for (int j = 0; j < N; j++) {
result[j] += (board[i-1][j] == 'D' ? 0 : 1);
}
// from left
for (int j = 1; j < N; j++) {
result[j] = Math.min((result[j-1] + (board[i][j-1] == 'R' ? 0 : 1)), result[j]);
}
// from right
for (int j = N - 2; j >= 0; j--) {
result[j] = Math.min((result[j+1] + (board[i][j+1] == 'L' ? 0 : 1)), result[j]);
}
}
for (int i = 0; i < N; i++) {
result[i] += (board[board.length-1][i] == 'D' ? 0 : 1);
}
return result;
}

分析

赋值的顺序很重要,必须要先算从上来的路径给该行附一个初始值。
Memory usage: N
Time: O(N*M)