글 읽기 - 어디선가 헤매고 있습니다 ㅠㅠ

superm 5년 전 0

제가 생각한 로직대로라면 구현이 되어야하는데

문제의 TC 말고 다른 질문검색에서 본 TC 중 몇개가 안됩니다 ㅠㅠ

그 예제를 아무리 봐도 어디에서 문제가 있는건지 잘 모르겠네요 ㅠㅠㅠ

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#define MAX 11
#define INF 987654321
using namespace std;

typedef pair<int, int> node;

int n,m,ans;
int nx1,ny1,nx2,ny2;

char map[MAX][MAX];
bool visited[MAX][MAX][MAX][MAX];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

queue<node> q;

node red,blue,hole;

bool is_hole(int x,int y){
    if(x == hole.first && y == hole.second) return true;
    else return false;
}

void tilt(int x1,int y1,int x2,int y2,int dir){
    
    // 빨간공을 기울임
    q.push(node(x1,y1));
    while(!q.empty()){
        int rx = q.front().first;
        int ry = q.front().second;
        q.pop();
        
        nx1 = rx + dx[dir];
        ny1 = ry + dy[dir];
        
        if(map[nx1][ny1] == 'O'){
            break;
        }else if(map[nx1][ny1] == '#'){
            nx1 = rx;
            ny1 = ry;
            break;
        }
        
        q.push(node(nx1,ny1));
    }
    
    // 만약 큐가 empty 상태가 아니라면 초기화
    if(!q.empty()){
        queue<node> empty;
        swap(q, empty);
    }
    
    // 파란공을 기울임
    q.push(node(x2,y2));
    while(!q.empty()){
        int bx = q.front().first;
        int by = q.front().second;
        q.pop();
        
        nx2 = bx + dx[dir];
        ny2 = by + dy[dir];
        
        if(map[nx2][ny2] == 'O'){
            break;
        }else if(map[nx2][ny2] == '#'){
            nx2 = bx;
            ny2 = by;
            break;
        }
        
        q.push(node(nx2,ny2));
    }
    
    // 만약 큐가 empty 상태가 아니라면 초기화
    if(!q.empty()){
        queue<node> empty;
        swap(q, empty);
    }
    
    // 만약 두개의 구슬이 겹쳤다면
    if(nx1==nx2 && ny1==ny2){
        // 구멍에서 겹친 경우 제외
        if(is_hole(nx1,ny1)) return;
        
        if(dir == 0){
            // Red 가 더 오른쪽에 있었다면
            if(y1 - y2 > 0){
                ny2--;
            }else{
                ny1--;
            }
        }else if(dir == 1){
            // Red 가 더 왼쪽에 있었다면
            if(y1 - y2 < 0){
                ny2++;
            }else{
                ny1++;
            }
        }else if(dir == 2){
            // Red 가 더 아래에 있었다면
            if(x1 - x2 > 0){
                nx2--;
            }else{
                nx1--;
            }
        }else{
            // Red 가 더 위에 있었다면
            if(x1 - x2 < 0){
                nx2++;
            }else{
                nx1++;
            }
        }
    }
}

void dfs(int x1,int y1,int x2,int y2,int cnt){
    // 최소보다 많거나 같은 경우
    if(cnt >= ans) return;
    
    // 횟수를 초과한 경우
    if(cnt > 10) return;
    
    // 구멍에 빨간공 IN 파란공 IN 경우
    if(is_hole(x1,y1) && is_hole(x2,y2)) return;
    
    // 구멍에 빨간공 OUT 파란공 IN 경우
    if(!is_hole(x1,y1) && is_hole(x2,y2)) return;
    
    // 구멍에 빨간공 IN 파란공 OUT 경우
    if(is_hole(x1,y1) && !is_hole(x2,y2)){
        ans = min(ans,cnt);
        return;
    }
    
    // 상 하 좌 우 기울이기
    for(int i=0; i<4; i++){
        
        // 보드를 기울여 nx1,ny1,nx2,ny2 를 얻는다
        tilt(x1,y1,x2,y2,i);
        
        if(!visited[nx1][ny1][nx2][ny2]){
            visited[nx1][ny1][nx2][ny2] = true;
            dfs(nx1,ny1,nx2,ny2,cnt+1);
            visited[nx1][ny1][nx2][ny2] = false;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::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<m; j++){
            cin >> map[i][j];
            
            if(map[i][j] == 'R'){
                red.first = i;
                red.second = j;
            }
            else if(map[i][j] == 'B'){
                blue.first = i;
                blue.second = j;
            }
            else if(map[i][j] == 'O'){
                hole.first = i;
                hole.second = j;
            }
        }
    }
    
    ans = INF;
    memset(visited, false, sizeof(visited));
    
    visited[red.first][red.second][blue.first][blue.second] = true;
    dfs(red.first,red.second,blue.first,blue.second,0);
    
    if(ans == INF)
        cout << -1 << "\n";
    else
        cout << ans << "\n";
    
    return 0;
}

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

문제

문제

출처

ICPC

어디선가 헤매고 있습니다 ㅠㅠ

superm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말