/**
#include<stdio.h>
int map[1001][1001] = {}, queue[2][1000001] = {}, dx[4] = {0, +1, 0, -1}, dy[4] = {-1, 0, +1, 0};
int n, m, front = -1, rear = -1, pi, pj;
void pop()
{
front ++;
pi = queue[0][front];
pj = queue[1][front];
}
void push(int i, int j)
{
//if (4 < 1 || 4 > 4 || 6 < 1 || 6 > 6)
if (i < 1 || i > n || j < 1 || j > m)
{
return ;
}
map[i][j] = 1;
rear ++;
queue[0][rear] = i;
queue[1][rear] = j;
}
void bfs(int i, int j)
{
for (int k = 0 ; k < 4 ; k ++)
{
if (map[i + dy[k]][j + dx[k]] == 0)
{
push(i + dy[k], j + dx[k]);
}
}
}
int main()
{
int i,j,k, cnt=0, day=0, mr=0, zero=0;
scanf("%d %d", &m, &n);
for (i = 1 ; i <= n ; i ++)
{
for (j =1 ; j <= m ; j ++)
{
scanf("%d", &map[i][j]);
if (map[i][j] == 1)
{
zero = 1;
push(i, j);
}
}
}
if (zero == 0)
{
printf("0");
return 0;
}
while (front != rear)
{
day ++;
mr = rear;
for (i = front + 1 ; i <= mr ; i ++)
{
pop();
bfs(pi, pj);
}
}
for (i = 1 ; i <= n ; i ++)
{
for (j = 1 ; j <= m ; j ++)
{
if (map[i][j] == 0)
{
printf("-1");
return 0;
}
}
}
printf("%d", day-1);
return 0;
}
#include<stdio.h>
int map[1001][1001] = {}, v[1001][1001] = {}, queue[2][1000001] = {}, dx[4] = {0, +1, 0, -1}, dy[4] = {-1, 0, +1, 0};
int n, m, front = -1, rear = -1, pi, pj, cnt = 0;
void push(int i, int j)
{
if (i < 1 || i > n || j < 1 || j > m)
{
return ;
}
v[i][j] = 1;
if (i == n && j == m)
{
printf("%d", cnt + 1);
exit(0);
}
rear ++;
queue[0][rear] = i;
queue[1][rear] = j;
}
void pop()
{
front ++;
pi = queue[0][front];
pj = queue[1][front];
}
void bfs(int i, int j)
{
for (int k = 0 ; k < 4 ; k ++)
{
int s = abs(map[i][j] - map[i + dy[k]][j + dx[k]]);
if (s <= 1 && v[i + dy[k]][j + dx[k]] == 0)
{
push(i + dy[k], j + dx[k]);
}
}
}
void view()
{
for (int i = 1 ; i <= n ; i ++)
{
for (int j = 1 ; j <= m ; j ++)
{
printf("%d ", v[i][j]);
}
puts("");
}
puts("");
}
int main()
{
int i, j, k, mr = 0;
scanf("%d %d", &n, &m);
for (i = 1 ; i <= n ; i ++)
{
for (j = 1 ; j <= m ; j ++)
{
scanf("%d", &map[i][j]);
}
}
v[1][1] = 1;
push(1, 1);
while (front != rear)
{
cnt ++;
mr = rear;
for (i = front + 1 ; i <= mr ; i ++)
{
pop();
bfs(pi, pj);
//view();
}
}
if (v[n][m] == 0)
{
printf("0");
return 0;
}
printf("%d", cnt);
return 0;
}
알고리즘
그리디알고리즘
동적계획법
**/