글 읽기 - 13460 구슬 탈출2

busyhuman 5년 전 0

안녕하세요.

이 문제에서 방문한 곳 처리를 어떻게해줘야하는지 궁금합니다.

예시 몇 개를 보니까 방문한 곳이어도 다시 방문하게 되는 경우가 있더군요.

그래서 단순히 방문을 체크해주는 것은 의미가 없다고 생각되어서 그냥 방문 수를 세는 방식으로 처리해줬습니다.

한 곳을 임의의 n번 방문하면 '아 이거는 구멍에 도달할 수 없는 것이다'라고 처리하여 -1을 출력했는 방식으로 처리했는데

간신히 큐가 안터지는 범위 내에서 휴리스틱으로 처리하긴했는데

이건 좀 잘못 푼 거같아서 원래 어떻게 풀어야하는건지 질문드립니다.

질문을 적고 나니 각 위치마다 상하좌우에서 온 것을 체크해야하나 생각이들긴했는데 잘 모르겠습니다.

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <list>
#include <queue>
#include <vector>
#include <deque>
#include <bitset>
#include <set>
#include <map>
using namespace std;
#define inf 2000000000
int n, m;
int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};
int check[11][11];
string s[11];
queue< pair<int,int> > red,blue;

int main(){
    int holex,holey;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++){
        cin >> s[i];
    }
queue<int> count;
    count.push(0);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j] == 'O'){
                holey = i;
                holex = j;
            } else if(s[i][j] == 'R'){
                red.push(make_pair(i,j));
                check[i][j]=1;
            } else if(s[i][j] == 'B'){
                blue.push(make_pair(i,j));
            }
        }
    }
    bool ccc=false;
    while(!red.empty()){
        
        int ry=red.front().first, rx=red.front().second, bx=blue.front().second, by=blue.front().first, cnt=count.front();
        if(ry == holey && rx == holex) break;
        if(ccc == true) break;
        red.pop();
        blue.pop();
        count.pop();
  
        for(int i=0;i<4;i++){
            bool putable = true;
            int imsiy = by, imsix =bx, obsy= 0, obsx =0;
            
            while(true){
                imsiy += dy[i];
                imsix += dx[i];
                if(s[imsiy][imsix] == '#'){
                        blue.push(make_pair(imsiy - dy[i] + obsy, imsix - dx[i] + obsx));
                     break;
                }
                else if(imsiy == ry && imsix == rx){
                     obsy = dy[i] * (-1);
                     obsx = dx[i] * (-1);
                } else if(s[imsiy][imsix] == 'O'){
                    putable = false;
                    break;
                }
            }
            
            if(!putable) continue;
            
            imsiy = ry, imsix = rx, obsy= 0, obsx =0;
            while(true){
                imsiy += dy[i];
                imsix += dx[i];
                if(s[imsiy][imsix] == '#'){
                     if(1350000 < ++check[imsiy - dy[i] + obsy][imsix - dx[i] + obsx]) ccc=true; // 최대 3000000
                        red.push(make_pair(imsiy - dy[i] + obsy, imsix - dx[i] + obsx));
                        count.push(cnt+1);
                     break;
                }
                else if(imsiy == by && imsix == bx){
                     obsy = dy[i] * (-1);
                     obsx = dx[i] * (-1);
                } else if(s[imsiy][imsix] == 'O'){
                         
                    red.push(make_pair(imsiy, imsix));
                    count.push(cnt+1);
                    break;
                }
            }
            
            
        }
    }

    if(red.empty() || ccc) cout << "-1";
    else cout << count.front();
}

djm03178 5년 전 1

한 번 움직여서 두 구슬이 모두 멈췄을 때의 좌표를 각각 (x1, y1)과 (x2, y2)라고 해봅시다. 이걸 하나의 상태로 보고 BFS를 하면 됩니다.

visited[x1][y1][x2][y2]와 같이 방문 체크를 할 수 있습니다.

busyhuman 5년 전 0

아하 그냥 둘 다 저장하는 방법이 있었네요. 감사합니다

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

문제

문제

출처

ICPC

13460 구슬 탈출2

busyhuman 5년 전 0

djm03178 5년 전 1

busyhuman 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말