691. 立方体IV

思路：记忆化搜索，f[i][j]表示以i,j为起点的最大步数，那么可得转移方程 f[i][j] = max(f[i][j+1],f[i+1][j],f[i-1][j],f[i][j-1])+1。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int f[N][N], g[N][N];
int n;
int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};

int dp(int x,int y){
    
    int v = f[x][y];
    if(v != -1) return v;
    
    v = 1;
    
    for(int i = 0; i < 4; i++){
    
        int a = dx[i] + x, b = dy[i] + y;
        if(a >=0 && a < n && b >=0 && b < n && g[a][b] == g[x][y] + 1){
    
            v = max(v, dp(a,b) + 1);
        }
    }
    
    return v;
}
int main()
{
    
    int T;
    scanf("%d", &T);
    
    for(int cases = 1; cases <= T; cases++){
    
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                scanf("%d", &g[i][j]);
        memset(f, -1, sizeof f);
        
        int id,cnt = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++){
    
                int t = dp(i,j);
                if(t > cnt || t >= cnt && id > g[i][j]){
    
                    cnt = t;
                    id = g[i][j];
                }
            }
        printf("Case #%d: %d %d\n", cases, id, cnt);
    }
    return 0;
}