글 읽기 - 틀린 부분을 전혀 모르겠습니다...

gazebo1 3년 전 2

처음엔 재귀로 바로 구현할 수 있겠다 싶었는데 제출할 때마다 계속 틀리네요...

풀이는 먼저 재귀함수에서 상어의 위치를 인자로 받아 그 위치의 물고기 포식 -> 남은 물고기 이동 -> 다음 위치 탐색 순으로 작성했습니다.

물고기의 번호와 방향은 각각 Map과 dir에 이차원 배열 형태로 저장했고, 물고기 번호로 위치를 참조하기 위해 pair 배열을 따로 하나 선언했습니다.

한 위치에서 다음 위치로 갈 때 현재 물고기의 위치와 방향도 전부 curMap, curDir, curPos라는 이름으로 저장했다가 한 위치로의 탐색이 끝난 후에 다시 복원하는 것도 확인했습니다.

반례 혹은 어디서 틀렸는지 알려주시면 감사하겠습니다.

#include <iostream>
#include <utility>
using namespace std;

typedef pair<int, int> pii;

int Map[4][4];
int dir[4][4];
int maxVal = 0;
pii Pos[20];
int dy[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int dx[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};

int next(int d) {return (d == 8 ? 1 : d + 1);}

void solve(int y = 0, int x = 0, int sum = 0) {
    sum += Map[y][x];
    maxVal = max(maxVal, sum);
    int curD = dir[y][x];
    Pos[Map[y][x]] = {0, 0};
    Map[y][x] = dir[y][x] = -1;
    for (int k = 1; k <= 16; k++) {
        if (Pos[k] == make_pair(0, 0)) continue;
        int i = Pos[k].first, j = Pos[k].second;
        int ny = i, nx = j, d = dir[i][j];
        int count = 1;
        for (count; count <= 8; count++) {
            ny = i + dy[d];
            nx = j + dx[d];
            if (ny < 0 || ny >= 4 || nx < 0 || nx >= 4 || (ny == y && nx == x)) {
                d = next(d); 
                continue;
            }
            break;
        }
        if (count > 8) continue;
        if (Map[ny][nx] != -1) Pos[Map[ny][nx]] = {i, j};
        Pos[k] = {ny, nx};
        int bm = Map[ny][nx], bd = dir[ny][nx];
        Map[ny][nx] = Map[i][j]; dir[ny][nx] = d;
        Map[i][j] = bm; dir[i][j] = bd;
    }
    int curMap[4][4];
    int curDir[4][4];
    pii curPos[20];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            curMap[i][j] = Map[i][j];
            curDir[i][j] = dir[i][j];
        }
    }
    for (int i = 1; i <= 16; i++) curPos[i] = Pos[i];
    
    int curY = y, curX = x;
    for (int t = 1; t <= 3; t++) {
        curY += dy[curD];
        curX += dx[curD];
        if (curY < 0 || curY >= 4 || curX < 0 || curX >= 4) break;
        if (Map[curY][curX] == -1) continue;
        solve(curY, curX, sum);
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                Map[i][j] = curMap[i][j];
                dir[i][j] = curDir[i][j];
            }
        }
        for (int i = 1; i <= 16; i++) Pos[i] = curPos[i];
    }
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> Map[i][j] >> dir[i][j];
            Pos[Map[i][j]] = {i, j};
        }
    }
    solve();
    cout << maxVal << '\n';
}

gazebo1 3년 전 0

20, 23 번째 줄의 먹힌 물고기 처리할 때 pair 를 (0, 0) 대신 (-1, -1)로 처리하니 AC 받았습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린 부분을 전혀 모르겠습니다...

gazebo1 3년 전 2

gazebo1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말