글 읽기 - 반례 찾습니다.

silvanas 5년 전 0

오늘도 고생이 많으십니다.

어찌어찌 혼자 반례를 찾아 수정 해보았으나 여전히 되지 않습니다.

어디서 놓치고 있는지 잘 모르겠는데.. 도와주시면 감사하겠습니다.

평범한 BFS로 풀었으며

x,y, d(방향)을 저장하여

현재방향과 방문할 d 의 방향이 다르면 거울을 설치해주어야 하므로 값을 증가시켜주는 식으로 풀었습니다.

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

using namespace std;
int W, H;
char map[101][101];
int visit[101][101];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

struct coor{
    int x,y,d;
};
vector<pair<int, int> > goal;

int BFS(int r, int c){
    queue<coor> q;
    coor s = {r,c,-1};
    q.push(s);
    visit[r][c] = 0;
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int d = q.front().d;
        q.pop();
        for(int i = 0 ; i < 4 ; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx > -1 && xx < H && yy > -1 && yy < W && map[xx][yy] != '*'){
                //벽이거나 방문할 값이 현재 값 + 1 이랑 작거나 같을때 갱신
                if(visit[xx][yy] == 0 || visit[x][y] + 1 <= visit[xx][yy]){
                    if(d == i){
                        visit[xx][yy] = visit[x][y];
                        coor s = {xx,yy,i};
                        q.push(s);
                    }else{
                        visit[xx][yy] = visit[x][y] + 1;
                        coor s = {xx,yy,i};
                        q.push(s);
                    }
                }
            }
        }
    }
    return visit[goal[1].first][goal[1].second]-1;
}

int main(){
    cin >> W >> H;
    for(int i = 0 ; i < H ; i++){
        string temp;
        cin>>temp;
        for(int j = 0 ; j < W ; j++){
            map[i][j] = temp[j];
            if(map[i][j] == 'C') goal.push_back(make_pair(i,j));
        }
    }
    
    cout << BFS(goal[0].first,goal[0].second)<<endl;
    return 0;
}

sgchoi5 5년 전 1

USACO 문제는 출제자의 TC 와 답이 공개가 되어 있습니다. 정 안되시면 참고하시길..

silvanas 5년 전 0

말씀 감사합니다.

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

문제

문제

출처

ICPC

반례 찾습니다.

silvanas 5년 전 0

sgchoi5 5년 전 1

silvanas 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말