CubeIV

Given a matrix with each cell holds an integer number while all numbers are distinct. As for a cell with number i, you can go from here to adjoined cells with number i+1. The question is starting from which number we can go farest.

In fact we can put all these numbers from 1 to N in an one dimensional array and from the matrix we can decide if we can go from i to i + 1(We let next[i] = true if so). Then we use dynamic programming method and from the largest number N to 1 we record the longest steps we can go from i in $DP[i]$. So we have:

$$DP[i]=\begin{cases} DP[i+1] & next[i]=true\\ 1 & otherwise \end{cases}$$

import java.io.*;
import java.util.*;

public class CubeIV {
    static private int[][] M = new int[1010][1010];
    static private boolean[] next = new boolean[1010 * 1010];
    static private int[] dp = new int[1010 * 1010];
    static private int[] dx = {-1, 0, 1, 0};
    static private int[] dy = {0, 1, 0, -1};
    private static String solve(int N) {
        for (int i = 1; i <= N * N; i++) {
            next[i] = false;
            dp[i] = 1;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int cur = M[i][j];
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < N && y >= 0 && y < N && M[x][y] == cur + 1) {
                        next[cur] = true;
                        break;
                    }
                }
            }
        }
        int max = 1;
        int pos = 1;
        for (int i = N * N; i >= 1; i--) {
            if (next[i]) dp[i] += dp[i + 1];
            if (max <= dp[i]) {
                max = dp[i];
                pos = i;
            }
        }
        return String.format("%d %d", pos, max);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int N = in.nextInt();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    M[i][j] = in.nextInt();
                }
            }
            System.out.printf("Case #%d: %s\n", t + 1, solve(N));
        }
    }
}