算法题，米粒与国际象棋问题，请大家帮帮忙

Question

在国际象棋的棋盘上面有 NxN个格。每个格里面有若干的米粒。一只小猪站在1x1的格里，小猪每次只能向高位的列或行移动。小猪会吃掉所经过的格子里面所有的米粒。请编写程序计算小猪能吃掉的米粒的最大值，并得出最大值时小猪的路径。

Answer 1

不好意思，没仔细看题目，分析题目容易知道，不管起始点在哪，终点一定在行号和列号均为最高的顶角，分析，从棋盘格子A移动到棋盘格子B，如果我们把B中含有的米粒数看成是图中的A源点到B源点的权，那么这个问题就转化成了求起点到顶角的最长路径，当然，我们只有最短路径的现成求法，所以变通一下，设棋盘中单个格子含有的最大米粒数为MAX，设A到B的权为 MAX 送去B中的米粒数，这样就可以用Dijkstra 或 Floyd 来求了

Answer 2

import java.util.*;
/*在国际象棋的棋盘上面有 NxN个格。每个格里面有若干的米粒。
*一只小猪站在1x1的格里，小猪每次只能向高位的列或行移动。
*小猪会吃掉所经过的格子里面所有的米粒。
*请编写程序计算小猪能吃掉的米粒的最大值，并得出最大值时小猪的路径。
*/
public class Test8{
/**走到第i行,第j列的能吃到的最大的米数应该是:
* 第i-1行第j列最大米数,第i行第j-1列最大米数,两者的最大者与第i行第j列米数之和
* 按上面的思路可以算出每一个格子的最大米数.算法中的一些变量:
* row,column分别表示棋盘的行数和列数.
* maxRiceGrains[][]表示走到每一个格子时能吃到的最大米数.
* pigTrace[i][j][0]和pigTrace[i][j][1]分别表示到达i,j的上一步的行,列号
* trace是一个保存路径的List.
*/
public static List<int[]> howManyRiceGrains(int[][] chessBoard){
int row=chessBoard.length;
int column=chessBoard[0].length;
int[][] maxRiceGrains=new int[row][column];
int[][][] pigTrace=new int[row][column][2];
maxRiceGrains[0][0]=chessBoard[0][0];

//第一行,的最大数:
//
for(int j=1;j<column;j++){
maxRiceGrains[0][j]=maxRiceGrains[0][j-1]+chessBoard[0][j];
pigTrace[0][j]=new int[]{0,j-1};
}

//求第i行第j列的最大米数,
//其中i行0列的最大数米数是i-1行0列最大米数与i行0列米数之和.
//走到i行j列,要么是从i-1行j列过来的,要么是从i行j-1列过来的,所以比较一下两者的最大米数,
//选最大的作为上一步.
//
for(int i=1;i<row;i++){
maxRiceGrains[i][0]=maxRiceGrains[i-1][0]+chessBoard[i][0];
pigTrace[i][0]=new int[]{i-1,0};
for(int j=1;j<column;j++){
if(maxRiceGrains[i-1][j]>maxRiceGrains[i][j-1]){
maxRiceGrains[i][j]=maxRiceGrains[i-1][j]+chessBoard[i][j];
pigTrace[i][j]=new int[]{i-1,j};
}else{
maxRiceGrains[i][j]=maxRiceGrains[i][j-1]+chessBoard[i][j];
pigTrace[i][j]=new int[]{i,j-1};
}
}
}

//从row-1行column-1列根据pigTrace中记录的上一步的行列号,倒推回0行0列
//就可以求出整个的路径.
//
List<int[]> trace=new ArrayList<int[]>();
int i=row-1,j=column-1;
trace.add(new int[]{i,j,maxRiceGrains[i][j]});
while(i!=0||j!=0){
int currentI=i;
i=pigTrace[currentI][j][0];
j=pigTrace[currentI][j][1];
trace.add(new int[]{i,j,maxRiceGrains[i][j]});

}
Collections.reverse(trace);
return trace;
}

public static void main(String[] args){
Random rand=new Random();
int[][] chessBoard=new int[4][4];
System.out.println("棋盘如下：");

//随机在棋盘的格子上放些米：
//
for(int i=0;i<chessBoard.length;i++){
for(int j=0;j<chessBoard[i].length;j++){
chessBoard[i][j]=rand.nextInt(10);
System.out.printf("%5d",chessBoard[i][j]);
}
System.out.println();
}

System.out.println("\n能吃到最多米的路径：\n");
List<int[]> trace=howManyRiceGrains(chessBoard);
System.out.println("行    列  最大米数");
for(int[] cell : trace){
for(int i:cell){
System.out.print(i+"      ");
}
System.out.println();
}
}
}
F:\java>java Test8
棋盘如下：
    0    9    4    1
    0    7    8    3
    4    5    3    1
    1    5    4    3能吃到最多米的路径：行    列  最大米数
0      0      0
0      1      9
1      1      16
1      2      24
2      2      27
3      2      31
3      3      34

Answer 3

确实是动态规划来得简单，下面是我翻译的java版代码
package testatwill;public class A {
//棋盘矩阵，数字表示米粒数
private int[][] Matrix = { { 2, 2, 3, 0, }, { 0, 3, 1, 1, }, { 1, 2, 2, 1, },
{ 4, 1, 2, 2 } };
//矩阵B存储所吃的最大米粒数
private int[][] B = new int[4][4];
//x,y为起点坐标
private int x, y;
A(int n, int m) {
x = n;
y = m;
}
public int max(int a, int b) {
return a > b ? a : b;
} public int findMaxSeq(int i, int j) {
if (i == x && j == y) {
B[x][y] = Matrix[x][y];
return B[x][y];
}
int left, up;
left = i > x ? findMaxSeq(i - 1, j) : 0;
up = j > y ? findMaxSeq(i, j - 1) : 0;
B[j][i] = max(left, up) + Matrix[i][j];
return B[j][i];
} public void PathPrint(int i, int j) {
if (i == x && j == y) {
System.out.printf("(%d, %d) = %d,", x, y, Matrix[x][y]);
return;
}
int up = j > 0 ? B[i][j - 1] : 0;
if (up == B[i][j] - Matrix[j][i])
PathPrint(i, j - 1);
else
PathPrint(i - 1, j);
System.out.printf("(%d, %d) = %d,",  j, i, Matrix[j][i]);
} public static void main(String[] args) {
A test = new A(0, 0);
System.out.printf("最大值为: %d \n路线: ", test.findMaxSeq(3, 3));
test.PathPrint(3, 3);
}}