-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBOJ2665.cpp
More file actions
73 lines (61 loc) · 1.65 KB
/
BOJ2665.cpp
File metadata and controls
73 lines (61 loc) · 1.65 KB
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
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 55
#define INF 2123456789
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
// p는 좌표값, black은 화이트로 만든 칸의 갯수
struct st{
pi p;
int black=0;
};
int n;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
// map은 입력 받아 온것 , visit은 해당 좌표까지 오는데 black의 최소 값
int map[MAX][MAX],visit[MAX][MAX];
char str[MAX];
queue<st> q;
int main() {
// 초기 map을 모두 -1로 설정한다.
fill_n(&map[0][0],MAX*MAX,-1);
fill_n(&visit[0][0],MAX*MAX,INF);
// 입력받아온다.
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%s",str);
for (int j = 1;j <=n; j++) {
map[i][j] = str[j - 1] - '0';
}
}
// 시작지점 넣어준다.
st s = {{1,1},0};
q.push(s);
// bfs를 돌려준다.
while(!q.empty()){
s = q.front();
q.pop();
for(int i=0;i<4;i++)
{
int y = s.p.first+dy[i], x =s.p.second+dx[i];
// 0 or 1만 방문해준다.
if(map[y][x]==-1)
continue;
// 이동하려는 칸이 흰색인 경우.
if(map[y][x]==1&&visit[y][x]>s.black){
visit[y][x]=s.black;
q.push({{y,x},s.black});
}
// 이동하려는 칸이 검은색인 경우.
if(map[y][x]==0&&visit[y][x]>(s.black+1)){
visit[y][x]=s.black+1;
q.push({{y,x},s.black+1});
}
}
}
// 결과값을 출력해준다.
printf("%d",visit[n][n]);
return 0;
}