View Code of Problem 3499

#include <stdio.h>

int count = 0;//迷宫总解法数
int step = 1;//第几步
int b[25] = { 0 };//存储当前路径解法
int c[100][25] = {0};//存储所有解法坐标
int back = 0;//判断当前是前进还是原路回退 （0前进，1回退）

void fun(int a[5][5], int i, int j) {
	if (i == 4 && j == 4) {
		b[step] = i * 10 + j;
		b[0] = step;				
		for (int i = 0;i < 25;i++) {
			c[count][i] = b[i];
		}							//二维数组每行首元素存该解法步数
		count++;					//解法数+1
		back = 1;					
		/*for (int i = 0;i < 25;i++) {
			printf("%d ", b[i]);
		}
		printf("终点\n");*/
		return;						//返回找其他路
	}//找到终点
	else {
		int flag = 0;					//标记位如果以下4个if都不成立 说明死胡同 原路返回
		a[i][j] = 1;				    //走过的路置为1
		if (j < 4 && !a[i][j + 1]) {
			flag = 1;
			b[step] = i * 10 + j;		//记录当前坐标
			step++;                     //步数+1
			fun(a, i, j + 1);			//走下一步
			if (back) {					//如果是回退回来flag变为0表示此路不通
				flag = 0;
				back = 0;				//继续寻找目前位置的其他出路
			}
		}                               //没在最右边并且右一格不是墙可以往右走
		if (i < 4 && !a[i + 1][j]) {
			flag = 1;
			b[step] = i * 10 + j;
			step++;
			fun(a, i + 1, j);
			if (back) {
				flag = 0;
				back = 0;
			}
		}//没在最下边并且下一格不是墙可以往下走

		if (j > 0 && !a[i][j - 1]) {
			flag = 1;
			b[step] = i * 10 + j;
			step++;
			fun(a, i, j - 1);
			if (back) {
				flag = 0;
				back = 0;
			}
		}//没在最左边并且左一格不是墙可以往左走

		if (i > 0 && !a[i - 1][j]) {
			flag = 1;
			b[step] = i * 10 + j;
			step++;
			fun(a, i - 1, j);
			if (back) {
				flag = 0;
				back = 0;
			}
		}//没在最上边并且上一格不是墙可以往右走

		if (!flag) {						//上下左右都不通，回退
			a[i][j] = 0;					//置0
			step--;							//步数-1
			back = 1;						//表示原路返回
			/*for (int i = 0;i < 25;i++) {
				printf("%d ", b[i]);
			}
			printf("死路\n");*/
			return;
		}
	}
	if (i == 0 && j == 0) {					//返回回原点结束递归
		return;
	}
}

int main() {
	int a[5][5];
	for (int i = 0;i < 5;i++) {
		for (int j = 0;j < 5;j++) {
			scanf("%d", &a[i][j]);
		}
	}
	fun(a, 0, 0);
	int min = 999;
	for (int i = 0;i < count;i++) {
		if (c[i][0] < min) {
			min = i;
		}
	}//找出步数最小的解
	for (int i = 1;i <= c[min][0];i++) {
		int x = c[min][i] / 10;
		int y = c[min][i] % 10;
		printf("(%d, %d)\n", x, y);
	}//格式输出
}