1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| //
// 2206_벽 부수고 이동하기.cpp
// AlgorithmCpp
//
// Created by 정경인 on 16/02/2019.
// Copyright © 2019 kyoungin. All rights reserved.
//
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#define p pair<int,int>
#define pp pair<p,p>
using namespace std;
vector<vector<int>> v,cnt;
//int arr[1001][1001][2];
//오른쪽 아래 왼쪽 위
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int check[102][102] ={0};
int minNum=1000;
int X,Y;
void bfs();
int main(){
int i,j;
scanf("%d %d",&Y,&X);
v.resize(Y+1); cnt.resize(Y+1);
for(i=1;i<=Y;i++){
v[i].resize(X+1,0);
cnt[i].resize(X+1,100000000);
for(j=1;j<=X;j++){
int temp;
scanf("%1d",&temp);
v[i][j]=temp;
}
}
bfs();
printf("%d\n",minNum);
}
void bfs(){
queue<pp> q;
q.push(pp(p(1,1),p(1,0))); //y,x 카운트수 , 벽수
cnt[1][1]=1;
while(!q.empty()){
int y,x,sum,wcnt;
y=q.front().first.first;
x=q.front().first.second;
sum=q.front().second.first;// 지나온 길의 합
wcnt = q.front().second.second;//지금까지 부순 벽 수.
if(y==Y && x==X){
minNum = sum;
return;
}
q.pop();
for(int i=0;i<4;i++){
if(x+dx[i] >0 && x+dx[i] <=X && y+dy[i] >0 && y+dy[i] <=Y){
if(wcnt ==0){
if(cnt[y+dy[i]][x+dx[i]] < cnt[y][x]+1 || check[y+dy[i]][x+dx[i]] ==1){
if(v[y+dy[i]][x+dx[i]]==1){ //벽이면
q.push(pp(p(y+dy[i],x+dx[i]),p(sum+1,wcnt+1)));
cnt[y+dy[i]][x+dx[i]] =cnt[y][x]+1;
check[y+dy[i]][x+dx[i]]=1;
}
else{ //벽아니면 큐에 넣음.
q.push(pp(p(y+dy[i],x+dx[i]),p(sum+1,wcnt)));
cnt[y+dy[i]][x+dx[i]] =cnt[y][x]+1;
}
}
}
else{ //wcnt ==1
if(cnt[y+dy[i]][x+dx[i]] > cnt[y][x]+1 && v[y+dy[i]][x+dx[i]]==0){
q.push(pp(p(y+dy[i],x+dx[i]),p(sum+1,wcnt)));
cnt[y+dy[i]][x+dx[i]] =cnt[y][x]+1;
}
}
}//if(x+dx[i] >0 && x+dx[i] <=X && y+dy[i] >0 && y+dy[i] <=Y)
} // for(int i=0;i<4;i++)
}//while
if(cnt[Y][X]==100000000)
minNum=-1;
return ;
}
|