반응형
프로그램 명: maze
제한시간: 1 초
도적들로부터 값진 보물을 훔쳐 달아나던 알리바바는 한 도시에 이르렀다. 그 도시는 전체가 마치 미로처럼 되어 있는 도시였는데 그 도시 한 쪽 끝에는 미리 준비해 놓은 배가 있어,도시 끝까지만 다다르면 도적들을 따돌릴 수 있다. 그런데 도적들은 이 도시에 대하여 잘아고 있기 때문에 도적들보다 먼저 출구에 다다르기 위해서는반드시 최단거리를 갖는 길로 가야만 한다.
도시의 지도가 주어질 때 최단 거리의 길을 찾는 프로그램을 작성하시오. 예를들어 도시의모양이 위와 같을 경우 입구에서 오른쪽으로 갈 경우 총 9 개의 블록(하얀 블록의 개수)를 지나 출구에 다다를 수 있다.
입력 형식
첫째 줄에 미로의 세로의 크기와 가로의 크기를 나타내는 자연수 N 과 M 이 이 주어지고 다음 N 줄에는 미로의 상태를 나타내는 M 개의 정수가 주어진다. 길은 0 으로 막힌 곳은 1 로 표시되며 모든 정보는 빈 칸 없이 붙어 있다. 입구는 항상 왼쪽 제일 아래 이고, 출구는 항상 오른쪽 제일 위이다. N 과 M 은 20 이하의 자연수이다.출력 형식
첫 줄에 최단 거리의 길로 갈 경우 거쳐야 하는 블록의 개수를 출력한다. 만약 출구에 이르는 길이 없다면 -1 을 출력한다.입출력 예
입력 5 5 00110 00010 00110 00000 01011 출력 9
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 | #include <stdio.h> #define MAX 25 int Min=MAX*MAX; int N, M; char Map[MAX][MAX]; int Visit[MAX][MAX]; int Dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; void input() { int i, j; scanf("%d %d", &N, &M); //N세로 M가로 for(i=0; i<N; i++) { scanf("%s", Map[i]); } } void dfs(int y, int x, int depth) { int i, j; int wX, wY; if(x<0 || y<0 || y>=N || x>=M) //맵의 범위를 벗어 날때 return; if(y == 0 && x == M-1) //도착할때 { if(depth < Min) Min = depth; return; } for(i=0; i<4; i++) { wX = x + Dir[i][0], wY = y + Dir[i][1]; if(Visit[wY][wX] == 0 && Map[wY][wX] == '0') { Visit[wY][wX] = 1; dfs(wY, wX, depth+1); Visit[wY][wX] = 0; } } } int main(void) { input(); dfs(N-1, 0, 1); if(Min == 0) printf("%-1\n"); else printf("%d\n", Min); return 0; } | cs |
반응형
'개발 > 알고리즘' 카테고리의 다른 글
| [greedy method] 스노보드/snowboard (0) | 2015.02.12 |
|---|---|
| [bfs] dam (0) | 2015.02.06 |
| [backtracking] eating_puzzle (0) | 2015.01.23 |
| [재귀] upstair (0) | 2015.01.23 |
| [dfs] orders (알파벳 사전식 정렬) (0) | 2015.01.23 |