~cpp //maze 최단경로일필요는 없음

#include <stdio.h>
#include <stdlib.h>

void input();
void process(int x,int y);
void output();

int print[100][2],cnt,finish_x,finish_y;
int data[51][51];

void main()
{
	system("cls");	
	input();
	process(1,1);
}

void input()
{
	FILE *fp=fopen("maze.txt","rt");
	fscanf (fp,"%d %d",&finish_x,&finish_y);
	for (int i=1;i<=finish_x;i++){
		for (int j=1;j<=finish_y;j++){
			fscanf (fp,"%d",&data[i][j]);
		}
	}
	fclose(fp);
}

void process(int x,int y)
{
	int dx[8]={-1,-1,-1,0,0,1,1,1},dy[8]={-1,0,1,-1,1,-1,0,1};
	if (x==finish_x && y==finish_y) {
		output();
		exit(-1);
	}
	for (int i=0;i<8;i++)
	{
		if (!data[x+dx[i]][y+dy[i]] && x+dx[i]>=1 && x+dx[i]<=finish_x && y+dy[i]>=1 && y+dy[i]<=finish_y){
			data[x+dx[i]][y+dy[i]]=1;
			print[cnt][0]=x+dx[i];
			print[cnt++][1]=y+dy[i];
			process(x+dx[i],y+dy[i]);
			data[x+dx[i]][y+dy[i]]=0;
			cnt--;
		}
	}
}

void output()
{
	printf ("1,1\n");
	for (int i=0;i<cnt;i++)
	{
		printf ("%d,%d\n",print[i][0],print[i][1]);
	}
}