글 읽기 - 4179 불! 틀린부분을 찾고있습니다.

134ean 2년 전 0

한턴씩 불 먼저 퍼트리고 사람이 움직이는 순으로 구현했습니다.

7%에서 계속 틀리는데 어떤 부분이 문제일까요..?

#include <bits/stdc++.h>

using namespace std;

int R,C;
char board[1001][1001];
int dist[1001][1001];
int dy[4] ={1,-1,0,0};
int dx[4] ={0,0,1,-1};
int pDist = 0;
bool mv;

int main()
{
    cin>>R>>C;
    
    queue<pair<int,int>> player;
    queue<pair<int,int>> fire;

    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++){
            cin>>board[i][j];
            if(board[i][j] == 'J'){
              player.push({i,j});
            } 
            else if(board[i][j] == 'F'){
              fire.push({i,j});
            } 
        }
    
    memset(dist,-1,sizeof(dist));
    dist[player.front().first][player.front().second] = 1;
    
    while(!player.empty()){
        
        // 불 먼저 bfs
        int sz = fire.size();
        for(int tmp=0;tmp<sz;tmp++){
            int hy = fire.front().first;
            int hx = fire.front().second;
            fire.pop();
            
            for(int i=0;i<4;i++){
                int ry = hy + dy[i];
                int rx = hx + dx[i];
                
                if(ry<0||rx<0||ry>=R||rx>=C) continue;
                if(board[ry][rx] == '#' || board[ry][rx] == '*') continue;
                
                board[ry][rx] = '*';
                fire.push({ry,rx});
            }
        }
        // 플레이어 bfs
        int sz2 = player.size();
        for(int k=0;k<sz2;k++){
            int py = player.front().first;
            int px = player.front().second;
            player.pop();
            mv = true; // 플레이어가 움직일 수 없으면 true 유지
            
            for(int i=0;i<4;i++){
                int y = py + dy[i];
                int x = px + dx[i];
                
                if(y<0||x<0||y>=R||x>=C) continue;
                if(board[y][x] != '.' || dist[y][x] != -1) continue;
                
                mv = false;
                if(y == 0 || x == 0 || y == R-1 || x == C-1){
                    dist[y][x] = dist[py][px] + 1;
                    pDist = dist[y][x];
                    while(!player.empty()) player.pop(); //도착하면 탈출
                    sz2 = 0; 
                    break;
                }
                else{
                    dist[y][x] = dist[py][px] + 1;
                    player.push({y,x});
                }
            }   
        }
        
        if(mv) break; // 움직을 수 없으면 탈출
    }
    
    if(mv) cout << "IMPOSSIBLE";
    else cout << pDist;
}

luniro 2년 전 2

반례

4 4
####
JF.#
#..#
#..#

134ean 2년 전 0

감사합니다 해결했습니다~

ejrdnjs96 2년 전 0

````

4 4
####
JF.#
#..#
#..#

````

이 반례의 답이 1 맞나요?

134ean 2년 전 0

네 1 맞습니다.

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

문제

문제

출처

ICPC

4179 불! 틀린부분을 찾고있습니다.

134ean 2년 전 0

luniro 2년 전 2

134ean 2년 전 0

ejrdnjs96 2년 전 0

134ean 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말