백준 29946 (C++) Koopamatk

최초 업로드: 2025-09-21 04:39:39

최근 수정 시간: 2025-09-21 04:39:39

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] Koopamatk

[문제 링크](https://www.acmicpc.net/problem/29946)

## 문제 설명

Speleoloogia on kahtlemata üks põnevamaid ja seiklusrikkamaid teadusi, mida on võimalik üldse ette kujutada. Muidugi kaasnevad seiklustega ka ohud. Aga ega üks päris ohutu asi ikka seiklus ei ole ka ju... Nii või naa, ettevaatusabinõudele vaatamata võib maa all igasuguseid ootamatusi juhtuda ja vahel on teadlastel vaja koobastest välja jõuda nii kiiresti kui vähegi võimalik.

Selleks ongi tarvis kirjutada programm, mis leiaks lühima tee mõne väljapääsuni.

## 입력

Faili esimesel real on koobastiku kaardi kõrgus $H$ ja laius $W$ ($1 \le H \le 100$, $1 \le W \le 100$). Järgmisel $H$ real on igaühel täpselt $W$ märki: koobastiku kaart, kus '<code>.</code>' märgib läbipääsetavat kohta, '<code>#</code>' koopa seina ja '<code>@</code>' uurimisgrupi algasukohta. Punkt reas 1 või $H$ või veerus 1 või $W$ märgib väljapääsu. Teadlased saavad igal sammul liikuda läbipääsetavale naaberruudule samas reas või samas veerus.

## 출력

Faili esimesele reale väljastada lühima koopast välja viiva tee pikkus ja järgmisele $H$ reale kaart, millel see tee on märgitud tärnidega ('<code>*</code>'). Kui minimaalse pikkusega teid on mitu, väljastada ükskõik milline neist. Kui väljapääsu ei ole, väljastada arv $-1$ ja esialgne kaart.

## 풀이
bfs 한번 해서 도착 지점을 찾고, 도착 지점에서 시작 지점까지 역추적하며 별을 찍으면 되는 문제입니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

struct pos {
    int x, y;
};

int cost[100][100];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
vector<string> board(100);
vector<vector<pos>> prv(100, vector<pos>(100));

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int h, w; cin >> h >> w;

pos start;
 for(int i=0;i<h;i++) {
 cin >> board[i];
 for(int j=0;j<w;j++) {
 if(board[i][j]=='@') {
 start = {i, j};
 }
 }
 }

pos finish = {-1, -1};
 fill(&cost[0][0], &cost[99][100], INF);
 queue<pos> q; q.push(start);
 cost[start.x][start.y]=0;
 while(!q.empty()) {
 auto cur = q.front(); q.pop();
 if(cur.x==0 || cur.x==h-1 || cur.y==0 || cur.y==w-1) {
 finish = cur;
 break;
 }
 for(int i=0;i<4;i++) {
 pos next = {cur.x+dx[i], cur.y+dy[i]};
 if(next.x<0 || next.x>=h || next.y<0 || next.y>=w || cost[next.x][next.y]!=INF || board[next.x][next.y]!='.') continue;
 prv[next.x][next.y] = cur;
 cost[next.x][next.y] = cost[cur.x][cur.y]+1;
 q.push(next);
 }
 }

if(finish.x==-1) {
 cout << "-1\n";
 } else {
 cout << cost[finish.x][finish.y] << '\n';
 while(finish.x!=start.x || finish.y!=start.y) {
 board[finish.x][finish.y]='*';
 finish = prv[finish.x][finish.y];
 }
 }
 for(int i=0;i<h;i++) cout << board[i] << '\n';
}
```