## 算法求解：强迫症的小明

SBaof 发布于 2015/06/14 21:41

1  2  5
10  11  6
12  12  7

1    6   5   8   3  1
10  11  6  5   6  8
12  12  7  11 15 23
4    5   11 13  9  15
4    6   3    8  7  23
7    6  14   5  17  19

0
public class Position {
private int Grid[][] = new int[20][20];
private int Result[][] = new int[20][20];
private int rows;
private int cols;

public Position() {

}

public Position(int rows, int cols) {
this.cols = cols;
this.rows = rows;
}

public void init() {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入迷宫的行数");
rows = scanner.nextInt();
System.out.println("请输入迷宫的列数");
cols = scanner.nextInt();
System.out.println("请输入" + rows + "行" + cols + "列的迷宫");
int temp = 0;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
temp = scanner.nextInt();
Grid[i][j] = temp;
Result[i][j] = 0;
}
}
System.out.println();
Result[0][0] = Grid[0][0];
}

public void find(int x, int y, int k) {
int row = x;
int col = y;

/**
* 向右 移动
*/
for (int step = 1; step <= k; step++) {
if (col + step < cols && Grid[row][col + step] > Grid[row][col]) {
if (Result[row][col] + Grid[row][col + step] > Result[row][col
+ step]) {
Result[row][col + step] = Result[row][col]
+ Grid[row][col + step];
find(row, col + step, k);
}
}
}

/**
* 向左移动
*/
for (int step = 1; step <= k; step++) {
if (col - step >= 0 && Grid[row][col - step] > Grid[row][col]) {
if (Result[row][col] + Grid[row][col - step] > Result[row][col
- step]) {
Result[row][col - step] = Result[row][col]
+ Grid[row][col - step];
find(row, col - step, k);
}
}
}

/**
* 向下移动
*/
for (int step = 1; step <= k; step++) {
if (row + step < rows && Grid[row + step][col] > Grid[row][col]) {
if (Result[row][col] + Grid[row + step][col] > Result[row
+ step][col]) {
Result[row + step][col] = Result[row][col]
+ Grid[row + step][col];
find(row + step, col, k);
}
}
}

/**
* 向上移动
*/
for (int step = 1; step <= k; step++) {
if (row - step >= 0 && Grid[row - step][col] > Grid[row][col]) {
if (Result[row][col] + Grid[row - step][col] > Result[row
- step][col]) {
Result[row - step][col] = Result[row][col]
+ Grid[row - step][col];
find(row - step, col, k);
}
}
}
}

public void print() {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
System.out.print(Result[i][j] + " ");
}
System.out.println();
}
}

public static void main(String[] args){
Position position=new Position();
position.init();
position.find(0,0,4);
position.print();
}
}
0

0

0

0

0

0