백트래킹 - 미로

#include<stdio.h>
int miro[10][10],chk[11][11]={0},path[100][2];
int maxpath[100][2],minpath[100][2];
int max=-9999,min=9999;
int row,col,st_x,st_y,maxcnt,mincnt,maxsum,minsum;
FILE *fp,*fp1;

void back(int x,int y,int sum,int cnt){
	int i,j;
	path[cnt][0]=x;
	path[cnt][1]=y;
	chk[x][y]=1;
	if(x==row && y==col){
		if(sum>max){
			for(i=1;i<=cnt;i++){
				maxpath[i][0]=path[i][0];
				maxpath[i][1]=path[i][1];
			}
			max=sum;
			maxcnt=cnt;
		}
		else if(sum<min){
			for(i=1;i<=cnt;i++){
				minpath[i][0]=path[i][0];
				minpath[i][1]=path[i][1];
			}
			min=sum;
			mincnt=cnt;
		}
		chk[x][y]=0;
	}
	else{
		if(!chk[x][y+1])
			back(x,y+1,miro[x][y+1]+sum,cnt+1);
		if(!chk[x+1][y])
			back(x+1,y,miro[x+1][y]+sum,cnt+1);
		if(!chk[x][y-1])
			back(x,y-1,miro[x][y-1]+sum,cnt+1);
		if(!chk[x-1][y])
			back(x-1,y,miro[x-1][y]+sum,cnt+1);
		chk[x][y]=0;
	}
}

main(){
	int i,j;
	fp=fopen("input.txt","r");
	fp1=fopen("output.txt","w");	
	fscanf(fp,"%d %d",&row,&col);
	for(i=1;i<=row;i++){
		for(j=1;j<=col;j++){
			fscanf(fp,"%d",&miro[i][j]);
		}
	}
	fscanf(fp,"%d %d",&st_x,&st_y);
	for(i=0;i<=row+1;i++){
		for(j=0;j<=col+1;j++){
			if(i==0 || i==row+1 || j==0 || j==col+1)
				chk[i][j]=1;
		}
	}
	back(st_x,st_y,miro[st_x][st_y],1);
	fprintf(fp1,"최대경로:");
	for(i=1;i<=maxcnt;i++)
		fprintf(fp1,"(%d,%d)",maxpath[i][0],maxpath[i][1]);
	fprintf(fp1,"\n최대합 : %d\n",max);
	fprintf(fp1,"최소경로:");
	for(i=1;i<=mincnt;i++)
		fprintf(fp1,"(%d,%d)",minpath[i][0],minpath[i][1]);
	fprintf(fp1,"\n최소합 : %d\n",min);
}