욕심쟁이 판다

12 Aug 2017

욕심쟁이 판다

현재 위치를 (x, y), 이동할 위치를 (nx, ny) 일경우

현재 최대 생존일수 + 1 이 이동할 자리의 기존 최대 생존일수 보다 클 경우에만 업데이트 한다
(다익스트라에서 최단거리 업데이트와 유사)
d[nx][ny] 값이 더 컸을 경우 이동하지 않는 것이 낫다.

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        if (d[i][j] == 0) {
            d[i][j] = 1;
            f(i, j);
        }
    }
}
static void f(int x, int y) {
    int nx, ny;

    for (int i = 0; i < 4; i++) {
        nx = x + dx[i];
        ny = y + dy[i];
        // (d[x][y] + 1 > d[ax][ay] ??
        if (isInRange(nx, ny) && map[x][y] < map[nx][ny] && d[x][y] + 1 > d[nx][ny]) {
            d[nx][ny] = d[x][y] + 1;

            max = Math.max(max, d[nx][ny]);
            f(nx, ny);
        }
    }
}