首页 > 动态规划 > 线性DP > Problem A.Cube IV-Google APAC 2015
2014
11-12

Problem A.Cube IV-Google APAC 2015

Problem

Vincenzo decides to make cube IV but only has the budget to make a square maze. Its a perfect maze, every room is in the form of a square and there are 4 doors (1 on each side of the room). There is a big number written in the room. A person can only move from one room to another if the number in the next room is larger than the number in his current room by 1. Now, Vincenzo assigns unique numbers to all the rooms (1, 2, 3, …. S2) and then places S2 people in the maze, 1 in each room where S is the side length of the maze. The person who can move maximum number of times will win. Figure out who will emerge as the winner and the number of rooms he will be able to move.

Input

The first line of the input gives the number of test cases, TT test cases follow. Each test case consists of S which is the side length of the square maze. Then S2 numbers follow like a maze to give the numbers that have been assigned to the rooms.

1 2 9 
5 3 8 
4 6 7

Output

For each test case, output one line containing “Case #x: r d”, where x is the test case number (starting from 1), r is the room number of the person who will win and d is the number of rooms he could move. In case there are multiple such people, the person who is in the smallest room will win.

Sample Input

2
2
3 4
1 2 

3
1 2 9 
5 3 8 
4 6 7

Sample Output

Case #1: 1 2
Case #2: 6 4

题目大意:每次只能往上下左右四个方向走,找出从哪个位置开始,可以走的路径最长。简单的动态规划,这里使用记忆化搜索。

/**
 * Created by GaoTong on 2014/11/9.
 * copyright: www.acmerblog.com
 */
public class Cube {
    static Scanner s = null;
    static int map[][] = null;
    static int dp[][];
    static int dir[][] = { {1,0},{-1,0},{0,1},{0,-1} };
    public static void main(String args[]) throws FileNotFoundException {
        s = new Scanner(System.in);
        int c = s.nextInt();
        for(int k=1; k<=c; k++){
            int n = s.nextInt();
            map = new int[n][n];
            dp = new int[n][n];
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++)
                    map[i][j] = s.nextInt();
            }
            int maxAns = 0;
            int posAns = 0;
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    int tmpAns = dfsDp(i, j);
                    if(maxAns < tmpAns){
                        maxAns = tmpAns;
                        posAns = map[i][j];
                    }else if(maxAns == tmpAns){
                        if(posAns > map[i][j]) posAns = map[i][j];
                    }
                }
            }
            System.out.println( "Case #" + k+": " + posAns + " " + maxAns);
        }
    }

   static boolean checkxy(int x,int y){
        return x>=0 && x<map.length && y >=0 && y<map.length;
    }

    public static int dfsDp(int x, int y){
        if(dp[x][y] > 0) return dp[x][y];
        for(int d=0; d<4; d++){
            int nextx = x+dir[d][0];
            int nexty = y+dir[d][1];
            if(checkxy(nextx,nexty) && map[nextx][nexty] == map[x][y]+1){
                return dp[x][y] = 1+ dfsDp(nextx, nexty);
            }
        }
        return dp[x][y] = 1;
    }
}

  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  3. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3