미로찾기

10X10의 미로에서 01부터 100까지 가는
복수의 이동경로가 있을 경우 이동은 북, 동, 남, 서 순으로 한다.

방 번호

(입구)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	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	(출구)100

입력
10행 10열의 1 또는 0의 값이 주어진다. (1은 벽)

출력
총 경로의 길이를 출력하고 행마다 각 방의 번호를 출력한다.

입력예시(input.txt)
0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 1 1 1
0 1 1 1 1 0 0 1 1 1
0 1 1 1 1 0 1 1 1 1
0 1 1 1 1 0 1 1 1 1
0 1 1 0 1 0 1 1 1 1
0 1 1 1 0 0 0 1 1 1
0 1 1 1 1 1 0 1 1 1
0 0 0 0 0 0 0 0 0 0

출력예시
19
1
11
21
22
23
24
25
26
36
46
56
66
76
77
87
97
98
99
100

#include <stdio.h> FILE *fp; int miro[13][13], path[101], flag=1; int i,j; int back(int y,int x, int lenth) { if(flag==0) return 0; if(x+y == 20) { flag=0; fp=fopen("output.txt","w"); fprintf(fp,"%d\n",lenth+1); for(i=0; i<lenth; i++) fprintf(fp,"%d\n",path[i]); fprintf(fp,"100\n"); } else if(miro[y][x]) return 0; miro[y][x]=1; //지나온 길 체크; path[lenth]=(y-1)*10 + x; back(y-1, x, lenth+1); //북 back(y, x+1, lenth+1); //동 back(y+1, x, lenth+1); //남 back(y, x-1, lenth+1); //서 } main() { for(i=0; i<=10; i++) //벽만들기 { miro[0][i]=1; miro[i][0]=1; miro[11][i]=1; miro[i][11]=1; } fp=fopen("input.txt","r"); for(i=1; i<=10; i++) { for(j=1; j<=10; j++) { fscanf(fp,"%d",&miro[i][j]); } } back(1, 1, 0); }

옛날 옛적 대회에서 풀어보았던 문제 올려보았습니다.