上海闵行网站建设,北京游戏软件开发公司,高端建造,263企业邮箱pop3设置迷宫问题——I
题目链接 思路
创建二维数组#xff0c;并实现输入
首先输入二维数组的行和列#xff1a;
int n, m;
scanf(%d%d, n, m);然后动态开辟二维数组#xff1a;
注#xff1a;对动态开辟还不太了解的同学可以看看#x1f449;C语言—…迷宫问题——I
题目链接 思路
创建二维数组并实现输入
首先输入二维数组的行和列
int n, m;
scanf(%d%d, n, m);然后动态开辟二维数组
注对动态开辟还不太了解的同学可以看看C语言——动态内存管理
int** nums (int**)malloc(sizeof(int*) * n);
for (int i 0; i n; i)
{nums[i] (int*)malloc(sizeof(int) * m);
}最后向二维数组输入数据形成迷宫
for (int i 0; i n; i)for (int j 0; j m; j)scanf(%d, nums[i][j]);实现找路FindWay
首先为了方便记录我们可以定义一个结构体来记录二维数组每一个位置的坐标
注对结构体操作不太了解的小伙伴看这里传送门
typedef struct Position
{int row;int col;
}POS;接着我们应该确定找路的整体思路
从上、下、左、右四个方向分别探路探路之前要对将要前进到区域进行有效性判断如果符合条件再前进否则选择下一个方向如果四个方向都无法前进那么说明是个死路就要进行回溯由此可以推出需要用递归算法实现由回溯的位置再次选择方向前进为了避免走相同的路我们应该在走过的每个点位做上标记例如修改为除01的数据
判断位置有效性Judge
bool Judge(int** nums, int n, int m, POS pos)
{/*如果数组越界或者该点位的数据不是0就说明该点位无效不能前进*/if (pos.col m || pos.col 0 ||pos.row n || pos.row 0 ||nums[pos.row][pos.col] ! 0){return false;}elsereturn true;
}FindWay主体
FindWay(int** nums, int n, int m, POS entry)
{nums[entry.row][entry.col] -1;//上POS next entry;next.row--;if (Judge(nums, n, m, next)){FindWay(nums, n, m, next)}//下next entry;next.row;if (Judge(nums, n, m, next)){FindWay(nums, n, m, next)}//左next entry;next.col--;if (Judge(nums, n, m, next)){FindWay(nums, n, m, next)}//右next entry;next.col;if (Judge(nums, n, m, next)){FindWay(nums, n, m, next)}
}这样写会造成一个问题经过调试我们可以发现这个函数并没有实现走到右下角出口便结束的功能这个函数结束时停留的位置会在出口处因为可以走的的地方全部被标记为-1当无路可走的时候就会回溯最后就会回到出口因此我们可以将FindWay()函数的返回值设定为bood类型当走到出口时就退出函数
bool FindWay(int** nums, int n, int m, POS entry)
{if(entry.row n - 1 entry.col m - 1)return true;nums[entry.row][entry.col] -1;//上POS next entry;next.row--;if (Judge(nums, n, m, next)){if (FindWay(nums, n, m, next))return true;}//下next entry;next.row;if (Judge(nums, n, m, next)){if (FindWay(nums, n, m, next))return true;}//左next entry;next.col--;if (Judge(nums, n, m, next)){if (FindWay(nums, n, m, next))return true; }//右next entry;next.col;if (Judge(nums, n, m, next)){if (FindWay(nums, n, m, next))return true;}return false;
}保存正确的路径
很容易想到我们可以用一个数组来保存我们每走过的下标位置。但是当我们进行回溯的时候又要不断对无效的路径进行删除可见只是单纯的用一个数组是不方便实现的。
我们可以用栈的“先入后出”的特性来实现
注对于栈的基本操作还不太熟悉的小伙伴可以看看栈的基本操作
每走到一个位置就将这个位置入栈如果走到的位置无法前进就说明这个点位是思路需要回溯每回溯一个点位就需要将这个点位删除出栈
bool FindWay(int** nums, int n, int m, POS entry)
{StackPush(STACK, entry);if(entry.row n - 1 entry.col m - 1)return true;nums[entry.row][entry.col] -1;//上POS next entry;next.row--;if (Judge(nums, n, m, next)){if (FindWay(nums, n, m, next))return true;}//下next entry;next.row;if (Judge(nums, n, m, next)){if (FindWay(nums, n, m, next))return true;}//左next entry;next.col--;if (Judge(nums, n, m, next)){if (FindWay(nums, n, m, next))return true; }//右next entry;next.col;if (Judge(nums, n, m, next)){if (FindWay(nums, n, m, next))return true;}StackPop(STACK);return false;
}打印路径
由于栈的“先入后出”的特性取出栈的数据只能从栈顶到栈底取因此如果我们直接对栈的数据进行打印那么这个路径就是倒序出口-入口的。
为了得到正序入口-出口的路径我们可以建立一个辅助栈先将原有栈的数据逐个出栈到辅助栈中再打印辅助栈的数据这样就可以做到正序打印路径了。
void PrintWay()
{ST* stack (ST*)malloc(sizeof(ST));StackInit(stack);while (!StackEmpty(STACK)){POS temp StackTop(STACK);StackPop(STACK);StackPush(stack, temp);}while (!StackEmpty(stack)){POS temp StackTop(stack);StackPop(stack);printf((%d,%d)\n, temp.row, temp.col);}
}实现代码
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef struct Position
{int row;int col;
}POS;typedef POS StackDataType;
typedef struct Stack
{StackDataType* data;int top;
}ST;ST STACK; //定义一个全局栈//初始化栈
void StackInit(ST* stack)
{stack-top 0;stack-data (POS*)malloc(sizeof(POS) * 100);
}//判断栈空
bool StackEmpty(ST* stack)
{return stack-top 0;
}//入栈
void StackPush(ST* stack, POS val)
{stack-data[(stack-top)] val;
}//出栈
void StackPop(ST* stack)
{assert(!StackEmpty(stack));stack-top--;
}//返回栈顶元素
StackDataType StackTop(ST* stack)
{return stack-data[stack-top - 1];
}//判断是否可以前进
bool Judge(int** nums, int n, int m, POS pos)
{if (pos.col m || pos.col 0 ||pos.row n || pos.row 0 ||nums[pos.row][pos.col] ! 0){return false;}elsereturn true;
}//找路
bool FindWay(int** nums, int n, int m, POS entry)
{//先将该位置入栈StackPush(STACK, entry);//判断是否已经到了出口if(entry.row n - 1 entry.col m - 1)return true;//为了防止走相同的路要对走过的路做标记nums[entry.row][entry.col] -1;//上POS next entry;next.row--;if (Judge(nums, n, m, next)){//如果到了出口直接返回if (FindWay(nums, n, m, next))return true;}//下next entry;next.row;if (Judge(nums, n, m, next)){//如果到了出口直接返回if (FindWay(nums, n, m, next))return true;}//左next entry;next.col--;if (Judge(nums, n, m, next)){//如果到了出口直接返回 if (FindWay(nums, n, m, next))return true; }//右next entry;next.col;if (Judge(nums, n, m, next)){//如果到了出口直接返回 if (FindWay(nums, n, m, next))return true;}//如果是死路就出栈并返回假说明没到出口StackPop(STACK);return false;
}void PrintWay()
{//创建一个辅助栈ST* stack (ST*)malloc(sizeof(ST));StackInit(stack);//将原始栈的数据放入辅助栈while (!StackEmpty(STACK)){POS temp StackTop(STACK);StackPop(STACK);StackPush(stack, temp);}//打印辅助栈的路径while (!StackEmpty(stack)){POS temp StackTop(stack);StackPop(stack);printf((%d,%d)\n, temp.row, temp.col);}
}int main()
{int n, m;scanf(%d%d, n, m);//动态申请二维数组int** nums (int**)malloc(sizeof(int*) * n);for (int i 0; i n; i){nums[i] (int*)malloc(sizeof(int) * m);}//输入for (int i 0; i n; i)for (int j 0; j m; j)scanf(%d, nums[i][j]);//初始化全局栈StackInit(STACK);//找路POS entry { 0,0 };FindWay(nums, n, m, entry);//打印路径PrintWay();return 0;
}
