算法求解:强迫症的小明

SBaof 发布于 2015/06/14 21:41
阅读 432
收藏 3
正方形网格中,每个格点有一定数量的宝石。小明从网格最左上(0,0)出发,采集宝石。小明每次横向或竖向移动不超过... k .个方格后,停下来采集宝石。强迫症的小明要求每次采集宝石数量不低于上一次,否则宁愿停止集。
注:
停下来采集宝石后,才能转向;
一次移动不超过 k 步即,可以是 1,2.…k
经过的格点的宝石数量没有要求;
例如 :

对如下网格,网格中的整数为宝石数:

1  2  5
10  11  6
12  12  7
当 k 为 1  时,最优值为 37 ; k 为 2 时最优值为 47
这个结果,小明仔细观察能轻易看出来。下面这个网格,当 k = 4 时呢,小明苦思一天也没
肯定的结果,请编程帮助可怜的小明求解吧
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
答案是 130
动态规划,回溯法都可以
加载中
0
SBaof
SBaof
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
如比如比
如比如比
一次可以移动1到k个格,为取得最大值,要利益最大来判断,你那个转向是什么意思?是向右动了就不能向左移动,向下移了就不能向上动了么?
名字好记点
名字好记点
回复 @SBaof : 是49吧?你说的是不低于,那么最后还有个12才对。
如比如比
如比如比
回复 @SBaof : 哦,是说在移动ing的过程中不能出现折线,只能直线直到一个要挖取的格为止。
SBaof
SBaof
就是只有挖了那个位置的宝石之后才能转向,比如当k=1时,最佳路径是1+2+5+6+11+12=37
0
0
SBaof
SBaof

动态规划可以搞定


0
SBaof
SBaof

那个不低于有问题应该是大于 每次移动四个方向上下左右 然后把每次挖去后获得的总宝石存入一个新表格 最后可以得出最大值


0
泡不烂的凉粉
泡不烂的凉粉
矛盾,说的是不低于,大于等于的意思,最优应该是,1-2-11-12-12=38
魔神翼
魔神翼
那为什么不是1-2-5-6-11-12-12?
泡不烂的凉粉
泡不烂的凉粉
写错了
泡不烂的凉粉
泡不烂的凉粉
好像我写错了
返回顶部
顶部