1861. 정사각형 방(D4)

아직 방문하지 않은 방이고, 

OPT[i][j] = 좌표 (i, j)에서 가질 수 있는 최대 값으로

이미 값을 가지고 있으면 해당 값을 바로 리턴하며, 아직 구하지 않은 겨우에는 4방향을 탐색하여 값을 계산한다.

OPT[i][j] = OPT[i+k][j+k] + 1;

#include <stdio.h>
#include <memory.h>
int map[1001][1001];
int opt[1001][1001];//최적값 저장
char end[1001][1001];//i,j가 완료되었나
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,1,0,-1 };
int n;
 
int search(int x, int y)
{
    int result = 1;
    for (int i = 0; i < 4; i++)
    {
        if (x + dx[i] >= 0 && x + dx[i] < n && y + dy[i] >= 0 && y + dy[i] < n)
        {//정상 범위일 때에만
            if (map[x][y] + 1 == map[x + dx[i]][y + dy[i]])
            {
                if (end[x + dx[i]][y + dy[i]] == 0)//아직 안찾음
                {
                    opt[x + dx[i]][y + dy[i]] = search(x + dx[i], y + dy[i]);
                    end[x + dx[i]][y + dy[i]] = 1;
                    return opt[x + dx[i]][y + dy[i]] + result;
                }
                else
                {
                    return opt[x + dx[i]][y + dy[i]] + result;
                }
            }
            else if (map[x][y] == map[x + dx[i]][y + dy[i]] + 1)
            {//여기 들어와짐?
                
            }
        }
    }
    return result;
}
 
int main(void) {
    setbuf(stdout, NULL);
    int T;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++)
    {
        memset(map, 0, sizeof(map));
        memset(opt, 0, sizeof(opt));
        memset(end, 0, sizeof(end));
        
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
                scanf("%d", &map[i][j]);
        }
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (end[i][j] == 0)
                {
                    opt[i][j] = search(i, j);
                    end[i][j] = 1;
                }
            }
        }
        int max = 0;
        int number = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (opt[i][j] > max)
                {
                    max = opt[i][j];
                    number = map[i][j];
                }
                else if (opt[i][j] == max)
                {
                    if (map[i][j] < number)
                        number = map[i][j];
                }
            }
        }
        printf("#%d %d %d\n", test_case, number, max);
    }
 
    return 0;
}