글 읽기 - 반례 혹시 알 수 있을까요?

shjv 5년 전 0

기존 테스트케이스와 제가만든 몇가지 테스트케이스는 모두 통과하는데,
틀린 케이스를 잘 못찾겠습니다.
계속 디버깅하다보니까 코드가 산으로갔네요...
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
//1:땅 / 0:절벽 / 2이상:수만큼 주기를 가지는 오작교
int arr[10][10];
int chk[10][10];
int n, m;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { -1,0,1,0 };
int ans = -1;
typedef struct s {
    int x;
    int y;
    //이동시간
    int cnt;
    //다리 만들면 1
    int make;
    //오작교이용한다음 1
    int cant;
}s;

struct cmp {
    bool operator()(s t, s u) {
         return t.cnt > u.cnt;
    }
};

void bfs() {
    s first = { 0,0,0,0,0};
    priority_queue<s,vector<s>,cmp> q;
    chk[0][0] = 1;
    q.push(first);
    while (!q.empty()) {
        int x = q.top().x;
        int y = q.top().y;
        int cnt = q.top().cnt;
        int make = q.top().make;
        int cant = q.top().cant;
        //cout << "x , y , cnt : " << x << ' ' << y << ' ' << cnt << ' ' << '\n';
        q.pop();
        if (x == n - 1 && y == n - 1) {
            if (ans == -1 || ans > cnt) {
                ans = cnt;
            }
            continue;
        }
        //4방향 탐색
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx >= 0 && nx < n&&ny >= 0 && ny < n) {
                //한칸 이동할 수 있는경우
                if (arr[nx][ny] == 1 && (chk[nx][ny] == 0 || chk[nx][ny] >= cnt + 1)) {
                    chk[nx][ny] = cnt+1;
                    q.push({ nx,ny,cnt + 1 ,make,0});
                }
                //오작교 만드는 경우
                else if (arr[nx][ny] == 0 && make==0 && cant==0) {
                    int checker = 0;
                    for (int dir2 = 0; dir2 < 4; dir2++) {
                        int nx2 = nx + dx[dir2];
                        int ny2 = ny + dy[dir2];
                        if (nx2 >= 0 && nx2<n && ny2>=0 && ny2<n && arr[nx2][ny2] == 0)
                            checker++;
                    }
                    if (checker < 2) {
                        for (int dir2 = 0; dir2 < 4; dir2++) {
                            int nx2 = nx + dx[dir2];
                            int ny2 = ny + dy[dir2];
                            if (nx2 >= 0 && nx2 < n&&ny2 >= 0 && ny2 < n&&arr[nx2][ny2] == 1) {
                                int tmp;
                                if (cnt<m) {
                                    if (chk[nx2][ny2] == 0 || chk[nx2][ny2] >= m + 1) {
                                        chk[nx2][ny2] = m + 1;
                                        q.push({ nx2,ny2, m + 1,1,1 });
                                    }
                                }
                                else {
                                    if (cnt%m == 0) {
                                        if (chk[nx2][ny2] == 0 || chk[nx2][ny2] >= cnt + 2) {
                                            chk[nx2][ny2] = cnt + 2;
                                            q.push({ nx2,ny2,cnt + 2,1,1 });
                                        }
                                    }
                                    else {
                                        int tmp = cnt;
                                        while (tmp%m != 0) {
                                            tmp++;
                                        }
                                        if (chk[nx2][ny2] == 0 || chk[nx2][ny2] >= tmp + 1) {
                                            chk[nx2][ny2] = tmp + 1;
                                            q.push({ nx2,ny2,tmp + 1,1,1 });
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
                //기존오작교 이용하는 경우
                else if(arr[nx][ny]>1 && cant==0){
                    int k = arr[nx][ny];
                    for (int dir2 = 0; dir2 < 4; dir2++) {
                        int nx2 = nx + dx[dir2];
                        int ny2 = ny + dy[dir2];
                        if (nx2 >= 0 && nx2 < n&&ny2 >= 0 && ny2 < n&&arr[nx2][ny2] == 1) {
                            int tmp;
                            if (cnt<k) {
                                if (chk[nx2][ny2] == 0 || chk[nx2][ny2] >= k + 1) {
                                    chk[nx2][ny2] = k + 1;
                                    q.push({ nx2,ny2, k + 1 ,make,1 });
                                }
                            }
                            else {
                                if (cnt%k == 0) {
                                    if (chk[nx2][ny2] == 0 || chk[nx2][ny2] >= cnt + 2) {
                                        chk[nx2][ny2] = cnt + 2;
                                        q.push({ nx2,ny2,cnt + 2 ,make,1 });
                                    }
                                }
                                else {
                                    int tmp = cnt;
                                    while (tmp%k != 0) {
                                        tmp++;
                                    }
                                    if (chk[nx2][ny2] == 0 || chk[nx2][ny2] >= tmp + 1) {
                                        chk[nx2][ny2] = tmp + 1;
                                        q.push({ nx2,ny2,tmp + 1 ,make,1 });
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    bfs();
    cout << ans;
    return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

반례 혹시 알 수 있을까요?

shjv 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
