글 읽기 - 반례가 있을까요?

alsgud3229 5년 전 0

큐에 push 할때마다 능력이 쓰인 횟수를 저장하는 구조체를 넣어주었고 visited도 3차원으로 하여 능력이 쓰인 횟수에 해당하는 visited를 참조하게 하였습니다.

로직에 문제가 있는건가요? 반례가 있을까요?

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int map[203][203];
int n,m,k;
int mdx[4] = {0,0,1,-1};
int mdy[4] = {1,-1,0,0};
int hdx[8] = {-2,-1,1,2,2,1,-1,-2};
int hdy[8] = {1,2,2,1,-1,-2,-2,-1};
bool visited[203][203][32];
struct Pair{
    int x, y, ability;
};
queue<Pair> Q;
int t = 0;
bool flag = false;

void BFS(){
    int size = Q.size();
    while(size--){
        int x = Q.front().x;
        int y = Q.front().y;
        int ab = Q.front().ability;
        Q.pop();
        if(x==n-1 && y==m-1){
            flag = true;
            return;
        }
        if(ab<k){
            for(int i=0; i<8; i++){
                int nx = hdx[i]+x;
                int ny = hdy[i]+y;
                if(0<=nx && nx<n && 0<=ny && ny<m){
                    if(visited[nx][ny][ab]==false && map[nx][ny]==0){
                        visited[nx][ny][ab]=true;
                        Pair p = {nx,ny,ab+1};
                        Q.push(p);
                    }
                }
            }
        }

        for(int i=0; i<4; i++){
            int nx = mdx[i]+x;
            int ny = mdy[i]+y;
            if(0<=nx && nx<n && 0<=ny && ny<m) {
                if(visited[nx][ny][ab]==false && map[nx][ny]==0){
                    visited[nx][ny][ab]=true;
                    Pair p2 = {nx, ny, ab};
                    Q.push(p2);
                }
            }
        }
    }
}

int main(){

    cin>>k>>m>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>map[i][j];
        }
    }

    visited[0][0][0]=true;
    Pair src = {0,0,0};
    Q.push(src);

    while(!Q.empty()){
        BFS();
        if(flag){
            break;
        }
        t++;
    }

    if(flag){
        cout<<t;
    }
    else{
        cout<<-1;
    }

    return 0;
}

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

문제

문제

출처

ICPC

반례가 있을까요?

alsgud3229 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말