/*
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
*/
#include<stdio.h>
#include<string.h>
int N, M; //N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다.
int map[ 1001 ] [ 1001 ] ;
int wallmap[ 1001 ] [ 1001 ] ;
int visit[ 1001 ] [ 1001 ] ; //
int vety[ ] = { 0 , 0 , 1 ,- 1 } ;
int vetx[ ] = { 1 ,- 1 , 0 , 0 } ;
int front, rear;
int min, tmp_min;
int wallmin= 987654321 ;
typedef struct q{
int y, x, chk;
} q;
q queue[ 1001 * 1001 ] ;
void enque( int y, int x, int chk)
{
q temp;
temp.y = y;
temp.x = x;
temp.chk = chk; //벽을 부순적이 있는 큐인 지 체크.
queue[ rear++ ] = temp;
}
q deque( )
{
return queue[ front++ ] ;
}
int BFS( )
{
int i, nexty, nextx, nextchk;
while ( rear != front)
{
q pop= deque( ) ;
// if(wallmin<visit[pop.y][pop.x]) return wallmin;
for ( i= 0 ; i< 4 ; i++ )
{
nexty = pop.y + vety[ i] ;
nextx = pop.x + vetx[ i] ;
nextchk = pop.chk ;
printf ( "wise %d --> [%d][%d]\n " , visit
[ pop.
y ] [ pop.
x ] , pop.
y , pop.
x ) ; if ( nexty == N && nextx == M) {
return visit[ pop.y ] [ pop.x ] + 1 ;
}
//맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다.
if ( nexty>= 1 && nexty<= N && nextx>= 1 && nextx<= M)
{
if ( map[ nexty] [ nextx] == 0 ) // 0은 이동가능한 구역
{
if ( visit[ nexty] [ nextx] == 0 )
{
visit[ nexty] [ nextx] = visit[ pop.y ] [ pop.x ] + 1 ;
printf ( "%d --> [%d][%d]\n " , visit
[ nexty
] [ nextx
] , nexty
, nextx
) ;
if ( nextchk== 1 )
enque( nexty, nextx, 1 ) ;
else
enque( nexty, nextx, 0 ) ;
}
}
if ( map[ nexty] [ nextx] == 1 && pop.chk == 0 )
{
if ( visit[ nexty] [ nextx] == 0 )
{
visit[ nexty] [ nextx] = visit[ pop.y ] [ pop.x ] + 1 ;
printf ( "벽 부수기%d --> [%d][%d]\n " , visit
[ nexty
] [ nextx
] , nexty
, nextx
) ; pop.chk = 1 ;
enque( nexty, nextx, 1 ) ;
}
}
}
}
}
return 987654321 ; //시루패
}
/*
int breakwall()
{
int i,j;
for(i=1;i<=N;i++){
for(j=1;j<=M;j++){
if(map[i][j]==1)
{
enque(1, 1);
map[i][j]=0;
int w=BFS();
if(wallmin>w)
wallmin=w;
map[i][j]=1;
front=rear=0;
memset(visit, 0, sizeof(visit));
}
}
}
return wallmin;
}
*/
int main( )
{
int i, j;
for ( i= 1 ; i<= N; i++ )
for ( j= 1 ; j<= M; j++ )
//인큐는 항상 (1,1)
visit[ 1 ] [ 1 ] = 1 ;
enque( 1 , 1 , 0 ) ;
int min= BFS( ) ;
//front=rear=0;
//memset(visit,0, sizeof(visit));
//벽을 부셔볼까요??
//int cmp=breakwall();
//mapcopy( wallmap , map);
//if(min>cmp)
//min=cmp;
if ( min== 987654321 ) {
return 0 ;
}
return 0 ;
}
LyoKTsOXTeydmCDtlonroKzroZwg7ZGc7ZiE65CY64qUIOunteydtCDsnojri6QuIOunteyXkOyEnCAw7J2AIOydtOuPme2VoCDsiJgg7J6I64qUIOqzs+ydhCDrgpjtg4DrgrTqs6AsIDHsnYAg7J2064+Z7ZWgIOyImCDsl4bripQg67K97J20IOyeiOuKlCDqs7PsnYQg64KY7YOA64K464ukLiDri7nsi6DsnYAgKDEsIDEp7JeQ7IScIChOLCBNKeydmCDsnITsuZjquYzsp4Ag7J2064+Z7ZWY66CkIO2VmOuKlOuNsCwg7J2065WMIOy1nOuLqCDqsr3roZzroZwg7J2064+Z7ZWY66CkIO2VnOuLpC4g7LWc64uo6rK966Gc64qUIOunteyXkOyEnCDqsIDsnqUg7KCB7J2AIOqwnOyImOydmCDsubjsnYQg7KeA64KY64qUIOqyveuhnOulvCDrp5DtlZjripTrjbAsIOydtOuVjCDsi5zsnpHtlZjripQg7Lm46rO8IOuBneuCmOuKlCDsubjrj4Qg7Y+s7ZWo7ZW07IScIOyEvOuLpC4KCuunjOyVveyXkCDsnbTrj5ntlZjripQg64+E7KSR7JeQIO2VnCDqsJzsnZgg67K97J2EIOu2gOyImOqzoCDsnbTrj5ntlZjripQg6rKD7J20IOyigCDrjZQg6rK966Gc6rCAIOynp+yVhOynhOuLpOuptCwg67K97J2EIO2VnCDqsJwg6rmM7KeAIOu2gOyImOqzoCDsnbTrj5ntlZjsl6zrj4Qg65Cc64ukLgoK66e17J20IOyjvOyWtOyhjOydhCDrlYwsIOy1nOuLqCDqsr3roZzrpbwg6rWs7ZW0IOuCtOuKlCDtlITroZzqt7jrnqjsnYQg7J6R7ISx7ZWY7Iuc7JikLgoK7J6F66ClCuyyq+ynuCDspITsl5AgTigxIOKJpCBOIOKJpCAxLDAwMCksIE0oMSDiiaQgTSDiiaQgMSwwMDAp7J20IOyjvOyWtOynhOuLpC4g64uk7J2MIE7qsJzsnZgg7KSE7JeQIE3qsJzsnZgg7Iir7J6Q66GcIOunteydtCDso7zslrTsp4Tri6QuICgxLCAxKeqzvCAoTiwgTSnsnYAg7ZWt7IOBIDDsnbTrnbzqs6Ag6rCA7KCV7ZWY7J6QLgoK7Lac66ClCuyyq+ynuCDspITsl5Ag7LWc64uoIOqxsOumrOulvCDstpzroKXtlZzri6QuIOu2iOqwgOuKpe2VoCDrlYzripQgLTHsnYQg7Lac66Cl7ZWc64ukLgoqLwojaW5jbHVkZTxzdGRpby5oPgojaW5jbHVkZTxzdHJpbmcuaD4KaW50IE4sTTsvL04oMSDiiaQgTiDiiaQgMSwwMDApLCBNKDEg4omkIE0g4omkIDEsMDAwKeydtCDso7zslrTsp4Tri6QuCmludCBtYXBbMTAwMV1bMTAwMV07CmludCB3YWxsbWFwWzEwMDFdWzEwMDFdOwppbnQgdmlzaXRbMTAwMV1bMTAwMV07Ly8KaW50IHZldHlbXT17MCwwLDEsLTF9OwppbnQgdmV0eFtdPXsxLC0xLDAsMH07CmludCBmcm9udCxyZWFyOwppbnQgbWluLHRtcF9taW47CmludCB3YWxsbWluPTk4NzY1NDMyMTsKCnR5cGVkZWYgc3RydWN0IHF7CglpbnQgeSx4LGNoazsKfXE7CgpxIHF1ZXVlWzEwMDEqMTAwMV07Cgp2b2lkIGVucXVlKGludCB5LGludCB4LGludCBjaGspCnsKCXEgdGVtcDsKCXRlbXAueT15OwoJdGVtcC54PXg7Cgl0ZW1wLmNoaz1jaGs7IC8v67K97J2EIOu2gOyInOyggeydtCDsnojripQg7YGQ7J24IOyngCDssrTtgawuCglxdWV1ZVtyZWFyKytdPXRlbXA7Cn0KCnEgZGVxdWUoKQp7CglyZXR1cm4gcXVldWVbZnJvbnQrK107Cn0KCgoKCmludCBCRlMoKQp7CglpbnQgaSxuZXh0eSxuZXh0eCxuZXh0Y2hrOwoJCXdoaWxlKHJlYXIgIT0gZnJvbnQpCgkJewoJCQkgcSBwb3A9ZGVxdWUoKTsKCQkJLy8gaWYod2FsbG1pbjx2aXNpdFtwb3AueV1bcG9wLnhdKQlyZXR1cm4gd2FsbG1pbjsKCgkJCSBmb3IoaT0wO2k8NDtpKyspCgkJCSB7CgkJCQkgbmV4dHkgPSBwb3AueSArIHZldHlbaV07CgkJCQkgbmV4dHggPSBwb3AueCArIHZldHhbaV07CgkJCQkgbmV4dGNoayA9IHBvcC5jaGs7CgkJCQkgCgkJCQlwcmludGYoIndpc2UgJWQgLS0+IFslZF1bJWRdXG4iLHZpc2l0W3BvcC55XVtwb3AueF0scG9wLnkscG9wLngpOwoJCQkJIGlmKG5leHR5ID09IE4gJiYgbmV4dHggPT0gTSl7CgkJCQkJcmV0dXJuIHZpc2l0W3BvcC55XVtwb3AueF0rMTsKCQkJCSB9CgkJCQkKCQkJCSAKLy/rp7Xsl5DshJwgMOydgCDsnbTrj5ntlaAg7IiYIOyeiOuKlCDqs7PsnYQg64KY7YOA64K06rOgLCAx7J2AIOydtOuPme2VoCDsiJgg7JeG64qUIOuyveydtCDsnojripQg6rOz7J2EIOuCmO2DgOuCuOuLpC4gCgkJCQkJaWYobmV4dHk+PTEgJiYgbmV4dHk8PU4gJiYgbmV4dHg+PTEgJiYgbmV4dHg8PU0pCgkJCQkJewoKCgkJCQkJCWlmKG1hcFtuZXh0eV1bbmV4dHhdPT0wKSAvLyAw7J2AIOydtOuPmeqwgOuKpe2VnCDqtazsl60KCQkJCQkJewoJCQkJCQkJCWlmKHZpc2l0W25leHR5XVtuZXh0eF09PTApCgkJCQkJCQkJewoJCQkJCQkJCQl2aXNpdFtuZXh0eV1bbmV4dHhdPXZpc2l0W3BvcC55XVtwb3AueF0rMTsKCQkJCQkJCQkJcHJpbnRmKCIlZCAtLT4gWyVkXVslZF1cbiIsdmlzaXRbbmV4dHldW25leHR4XSxuZXh0eSxuZXh0eCk7CgoJCQkJCQkJCWlmKG5leHRjaGs9PTEpCgkJCQkJCQkJZW5xdWUobmV4dHksIG5leHR4LCAxKTsKCQkJCQkJCQkKCQkJCQkJCQllbHNlCgkJCQkJCQkJZW5xdWUobmV4dHksIG5leHR4LDApOwoKCQkJCQkJCQkKCQkJCQkJCQl9CgkJCQkJCX0KCgoJCQkJCQkJaWYobWFwW25leHR5XVtuZXh0eF09PTEgJiYgIHBvcC5jaGs9PTApCgkJCQkJCQl7CQoKCQkJCQkJCQkJaWYodmlzaXRbbmV4dHldW25leHR4XT09MCkKCQkJCQkJCQkJewoJCQkJCQkJCQkJdmlzaXRbbmV4dHldW25leHR4XT12aXNpdFtwb3AueV1bcG9wLnhdKzE7CgkJCQkJCQkJCQlwcmludGYoIuuyvSDrtoDsiJjquLAlZCAtLT4gWyVkXVslZF1cbiIsdmlzaXRbbmV4dHldW25leHR4XSxuZXh0eSxuZXh0eCk7CgkJCQkJCQkJCQlwb3AuY2hrPTE7CgkJCQkJCQkJCQllbnF1ZShuZXh0eSwgbmV4dHgsMSk7CgoJCQkJCQkJCQl9CgkJCQkJCQl9CgkKCgoKCQkJCQl9CgkJCSB9CgkJfQoJCXJldHVybiA5ODc2NTQzMjE7Ly/si5zro6jtjKgKfQoKLyoKaW50IGJyZWFrd2FsbCgpCnsKCWludCBpLGo7Cglmb3IoaT0xO2k8PU47aSsrKXsKCSAgZm9yKGo9MTtqPD1NO2orKyl7CgkJCQlpZihtYXBbaV1bal09PTEpCgkJCQkJewoJCQkJCQllbnF1ZSgxLCAxKTsKCQkJCQkJbWFwW2ldW2pdPTA7CgkJCQkJCWludCB3PUJGUygpOwoJCQkJCQlpZih3YWxsbWluPncpCgkJCQkJCQl3YWxsbWluPXc7CgkJCQkJCW1hcFtpXVtqXT0xOwoJCQkJCQlmcm9udD1yZWFyPTA7CgkJCQkJCW1lbXNldCh2aXNpdCwgMCwgc2l6ZW9mKHZpc2l0KSk7CgkJCQkJfQoJCX0KCX0KCXJldHVybiB3YWxsbWluOwp9CiovCgppbnQgbWFpbigpCnsKCWludCBpLGo7CglzY2FuZigiJWQlZCIsJk4sJk0pOwoJZm9yKGk9MTtpPD1OO2krKykKCSAgZm9yKGo9MTtqPD1NO2orKykKCQkJc2NhbmYoIiUxZCIsJm1hcFtpXVtqXSk7Ci8v7J247YGQ64qUIO2VreyDgSAoMSwxKQp2aXNpdFsxXVsxXT0xOwplbnF1ZSgxLDEsMCk7CmludCBtaW49QkZTKCk7Ci8vZnJvbnQ9cmVhcj0wOwovL21lbXNldCh2aXNpdCwwLCBzaXplb2YodmlzaXQpKTsKLy/rsr3snYQg67aA7IWU67O86rmM7JqUPz8KLy9pbnQgY21wPWJyZWFrd2FsbCgpOwovL21hcGNvcHkoIHdhbGxtYXAgLCBtYXApOwoKLy9pZihtaW4+Y21wKQoJLy9taW49Y21wOwoKaWYobWluPT05ODc2NTQzMjEpewoJcHJpbnRmKCItMSIpOwoJcmV0dXJuIDA7Cn0KCnByaW50ZigiJWQiLG1pbik7CgoKCnJldHVybiAwOwp9Cg==