问题遇到的现象和发生背景
用回溯法解决迷宫问题,但是在回溯的时候会将正确路径(已标记的元素)也再次返回为0,有没有解决方法,谢谢!
用代码块功能插入代码,请勿粘贴截图
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define SIZE 3
int a[SIZE][SIZE];
int init_r=0, init_c=0;//定义起点
int Fina_r = SIZE-1, Fina_c = SIZE-1;//定义终点
//右第1,下第2,左,上
int dr[] = {0,1 ,0,-1};
int dc[] = {1,0 ,-1,0};
int Can_place(int row, int col)
{
if (row >= 0 && row <= SIZE && col >= 0 && row <= SIZE && a[row][col] == 0)//判断是否越界以及下一步是否可走
{
return 1;
}
else
return 0;
}
int Finally(int row, int col)
{
if (row == Fina_r && col == Fina_c)
{
return 0;
}
}
void Search(int* row, int* col)
{
int r, c;//下一步的位置坐标
a[* row][* col] = 1;//标记为已走过
if (Finally(*row, *col)!=0)//判断是否到终点
{
for (int i = 0; i < 4; i++)
{
r = (*row) + dr[i];
c = (*col) + dc[i];
if (Can_place(r, c))
{
Search(&r, &c);
}
}
a[*row][*col] = 0;//回退
}
}
void Init(int* row,int* col)
{
int i = 0;
int j = 0;
row = init_r;
col = init_c;
printf("请输入迷宫(-1表示墙壁,0表示通路):");
for (int i = 0; i < SIZE; i++)
{
for (int j = 0; j < SIZE; j++)
{
scanf("%d",&a[i][j]);
}
}
}
void Print()
{
int i = 0;
int j = 0;
for (i = 0; i < SIZE; i++)
{
for (j = 0; j < SIZE; j++)
{
printf("%3d", a[i][j]);
}
printf("\n");
}
}
int main()
{
int row = 0;
int col = 0;
//初始化迷宫,初始化起点
Init(&row,&col);
Search(&row,&col);
Print();
return 0;
}
运行结果及报错内容
正确路径会被回溯为0