#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;
typedef struct point {
int x=0;
int y=0;
int b=0;
}points;
int world[1100][1100];
int visited[1100][1100][2];
int x_move[4] = { 0,0,-1,1 };
int y_move[4] = { 1,-1,0,0 };
int n=0;
int m=0;
queue<point> que;
bool is_inside(int nx, int ny) {
if(0<nx && nx<m+1 && 0<ny && ny<n+1) {
return true;
}
else {
return false;
}
}
int main()
{
points p;
scanf("%d %d", &n, &m);
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
scanf("%1d", &world[i][j]);
}
}
p.x = 1;
p.y = 1;
p.b= 1;
que.push(p);
while(!que.empty()) {
int xpos = que.front().x;
int ypos = que.front().y;
int block = que.front().b;
que.pop();
if(ypos==n &&xpos ==m) {
printf("%d",visited[ypos][xpos][block] +1);
return 0;
}
for(int i=0; i<4; i++) {
int mx = xpos+x_move[i];
int my = ypos+y_move[i];
if(is_inside(mx, my) == true) {
if(world[my][mx] == 1 && block==1) {
visited[my][mx][block-1] = visited[ypos][xpos][block]+1;
p.x = mx;
p.y = my;
p.b = block-1;
que.push(p);
}
if(world[my][mx] == 0 && visited[my][mx][block] == 0) {
visited[my][mx][block] = visited[ypos][xpos][block] +1;
p.x = mx;
p.y = my;
p.b = block;
que.push(p);
}
}
}
}
printf("-1");
return 0;
return 0;
}
'알고리즘' 카테고리의 다른 글
백준 13339 단어수학 (1) | 2023.03.09 |
---|---|
백준 14502 연구소 c++ (dfs bfs) (0) | 2023.03.08 |
[알고리즘] 백준11726 - 2xn타일링 c++ (0) | 2023.01.28 |
댓글