定义一个二维数组 N*M ，如 5 × 5 数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
数据范围： ， 输入的内容只包含
[编程题]迷宫问题
- 热度指数：196706 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
输出描述:
左上角到右下角的最短路径，格式如样例所示。
示例1
输入
5 5 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
输出
(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)
示例2
输入
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0
输出
(0,0) (1,0) (2,0) (3,0) (4,0) (4,1) (4,2) (4,3) (4,4)
说明
注意：不能斜着走！！
找这道题练习了一下堆栈：
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct stack{
int loc[2];
struct stack* next;
}Stack;
typedef Stack* pStack;
void push(int x, int y, pStack *ppstack){
pStack temp = (pStack)malloc(sizeof(Stack));
temp->loc[0] = x, temp->loc[1] = y;
temp->next = *ppstack;
*ppstack = temp;
}
_Bool isEmpty(pStack pstack){
return pstack==NULL;
}
_Bool pop(pStack *ppstack, int *res){
if(isEmpty(*ppstack)) return false;
res[0] = (*ppstack)->loc[0];
res[1] = (*ppstack)->loc[1];
pStack temp = *ppstack;
*ppstack = (*ppstack)->next;
free(temp);
return true;
}
void print_solution(pStack pstack){
int res[2];
if(pop(&pstack, res)){
print_solution(pstack);
} else return;
printf("(%d,%d)\n", res[0], res[1]);
}
int main() {
int a, b;
scanf("%d %d", &a, &b);
int **maze = (int**)malloc(sizeof(int*)*a);
for (int i=0;i<a;i++){
*(maze+i) = (int*)malloc(sizeof(int)*b);
for(int j=0;j<b;j++){
scanf("%d", &maze[i][j]);
}
}
// 当前坐标
int x, y;
int popres[2];
// 创建空stack
pStack pstack = (pStack)malloc(sizeof(Stack));
pstack->loc[0] = 0, pstack->loc[1] = 0;
// 更新迷宫
maze[0][0] = 1;
while (!isEmpty(pstack)) {
x = pstack->loc[0], y = pstack->loc[1];
if((x==a-1)&&(y==b-1)){
break; // 找到迷宫终点
}
else if((x<a-1)&&(maze[x+1][y]==0)){
push(x+1, y, &pstack);
maze[x+1][y] = 1;
}
else if((y<b-1)&&(maze[x][y+1]==0)){
push(x, y+1, &pstack);
maze[x][y+1] = 1;
}
else if((x-1>=0)&&(maze[x-1][y]==0)){
push(x-1, y, &pstack);
maze[x-1][y] = 1;
}
else if((y-1>=0)&&(maze[x][y-1]==0)){
push(x, y - 1, &pstack);
maze[x][y-1] = 1;
}
else{
if(!pop(&pstack, popres)){
printf("mase no solution\n");
return 0;
}
}
}
print_solution(pstack);
return 0;
}
发表于 2024-01-24 16:39:11
回复(0)
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 100
#define UP 1
#define RIGHT 2
#define DOWN 3
#define LEFT 4
typedef struct{
int x;
int y;
}Position;
typedef struct{
int top;
Position position[N];
} Stack;
void push(Stack* stack, Position pos)
{
stack->top++;
stack->position[stack->top].x = pos.x;
stack->position[stack->top].y = pos.y;
}
void push_pos(Position position[], int bit, Position pos)
{
position[bit].x = pos.x;
position[bit].y = pos.y;
}
int pop(Stack* stack)
{
if(stack->top > -1){
stack->top--;
return 0;
}
return -1;
}
Position GetNextPos(int direction, Position curPos)
{
Position nextPos;
switch(direction){
case UP:
nextPos.x = curPos.x;
nextPos.y = curPos.y - 1;
break;
case RIGHT:
nextPos.x = curPos.x+1;
nextPos.y = curPos.y;
break;
case DOWN:
nextPos.x = curPos.x;
nextPos.y = curPos.y + 1;
break;
case LEFT:
nextPos.x = curPos.x-1;
nextPos.y = curPos.y;
break;
default:
break;
}
return nextPos;
}
bool JudgeIsValid(Position pos[], int posBit, Position nextPos, int n, int m)
{
if(nextPos.x < 0 || nextPos.y < 0){
return false;
}
if(nextPos.x >= m || nextPos.y >= n){
return false;
}
for(int i = 0; i <= posBit; i++){
if(pos[i].x == nextPos.x && pos[i].y == nextPos.y){
return false;
}
}
return true;
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
int maze[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
scanf("%d", &maze[i][j]);
}
}
Stack stack_pos; // 用栈记录走过的位置点
Position pos[N]; // 记录所有走过的位置
Position curPos;
int posBit = -1;
stack_pos.top = -1;
curPos.x = 0, curPos.y = 0;
push(&stack_pos, curPos);
push_pos(pos, ++posBit, curPos);
while(1){
Position nextPos;
int flag = 1;
for(int i = 1; i <= 4; i++){
nextPos = GetNextPos(i, curPos);
if(JudgeIsValid(pos, posBit, nextPos, n, m)){
if(maze[nextPos.y][nextPos.x] == 1){
if(i == LEFT){
flag = 0;
}
continue;
}
curPos.x = nextPos.x;
curPos.y = nextPos.y;
push(&stack_pos, curPos);
push_pos(pos, ++posBit, curPos);
if(curPos.x == m-1 && curPos.y == n-1){
flag = 2;
}
break;
}else{
if(i == LEFT){
flag = 0;
}
}
}
if(flag == 0){
pop(&stack_pos);
curPos.x = stack_pos.position[stack_pos.top].x;
curPos.y = stack_pos.position[stack_pos.top].y;
}
if(flag == 2){
break;
}
}
for(int i = 0; i <= stack_pos.top; i++){
printf("(%d,%d)\n", stack_pos.position[i].y, stack_pos.position[i].x);
}
}
发表于 2023-10-06 17:44:23
回复(0)
第一次用DFS做题，向掌握DFS前进一小步#include <stdio.h> int next[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; int mark[10][10]; int path[100][2]; int main() { int row,col; int map[10][10]; void dfs(int x,int y,int step,int row,int col,int next[4][2],int map[10][10]); while (scanf("%d %d", &row, &col) != EOF) { for(int i=0;i<row;i++) for(int j=0;j<col;j++) scanf("%d",&map[i][j]); mark[0][0] = 1; path[0][0] = 0; path[0][1] = 0; dfs(0,0,1,row,col,next,map); } return 0; } void dfs(int x,int y,int step,int row,int col,int next[4][2],int map[10][10]){ int nx,ny,i; if(x==row-1&&y==col-1){ for(int j=0;j<step;j++){ printf("(%d,%d)\n",path[j][0],path[j][1]); } return; } if(map[x][y]==1){ return; } for(i=0;i<4;i++){ nx = x + next[i][0]; ny = y + next[i][1]; if(nx<0||nx>row-1||ny<0||ny>col-1) continue; if(mark[nx][ny]==0){ path[step][0] = nx; //保存路径 path[step][1] = ny; mark[nx][ny]=1; dfs(nx,ny,step+1,row,col,next,map); mark[nx][ny]=0; } } }
发表于 2023-04-25 22:02:59
回复(0)
#include <stdio.h>
void f(int *a,int *b,int x ,int y ,int i,int pos);
int n,m; //n行，m列；
int main() {
scanf("%d %d",&n,&m);
int a[n*m];
for(int i=0 ; i<m*n ;i++) scanf("%d",&a[i]);
int b[200]={0};
int i=0,j=0;
f(a,b,0,0,0,0);
return 0;
}
void f(int *a,int *b ,int x , int y ,int i,int pos){
b[i*2]=x;
b[i*2+1]=y;
if(x==n-1&&y==m-1) {
for(int j=0 ,k=0;j<i+1;j++,k+=2)
printf("(%d,%d)\n",b[k],b[k+1]);
}
int derication[4]={1,1,1,1};
if(y==0||pos==3||a[x*m+y-1]==1) derication[3]=0; //不能朝左
if(y==m-1||pos==1||a[x*m+y+1]==1) derication[1]=0; //不能向右
if(x==0||pos==0||a[(x-1)*m+y]==1) derication[0]=0; //不能向上
if(x==n-1||pos==2||a[(x+1)*m+y]==1) derication[2]=0; //不能向下
if(derication[0]) f(a, b, x-1, y, i+1, 2);
if(derication[1]) f(a, b, x, y+1, i+1, 3);
if(derication[2]) f(a, b, x+1, y, i+1, 0);
if(derication[3]) f(a, b, x, y-1, i+1, 1);
}
// 不受控制的递归，只好在经过终点时赶紧输出了，我该怎么办？
发表于 2023-04-08 23:50:18
回复(0)
#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#define MAX 100 //迷宫最大
int use[MAX][MAX]; //在判断路径是否能走时的最大矩阵
int maze[MAX][MAX]; //最大矩阵
int way[MAX][2]; //路径存储
int wid, lon; //实际矩阵长款
int win = 0; //是否已经走完矩阵
int stemp = 0; //走完矩阵时的步数
void ssss(int dir, int a, int b, int stemp_number); //dir初始方向，a,b当前位置坐标，stemp_number当前路径步数。
int main() {
scanf("%d %d", &wid, &lon); //读入矩阵长宽
for (int i = 0; i < wid; i++) {
for (int n = 0; n < lon; n++) {
scanf("%d", &maze[i][n]); //读入矩阵
use[i][n] = maze[i][n]; //初始化使用矩阵，有墙不能走
}
}
way[0][0] = 0;
way[0][1] = 0; //初始路径（0,0)
ssss(1, 0, 0, 0); //初始方向dir可随意，设置初始走向位置0，0;初始步数为0;
for (int i = 0; i < stemp; i++) {
printf("(%d,%d)\n", way[i][0], way[i][1]);
}
return 0;
}
void ssss(int dir, int a, int b, int stemp_number) {
if (a < 0 || a >= wid || b < 0 || b >= lon)
return; //如果走出地图边界则无法前进
if (use[a][b] == 1)
return; //不能走通则无法前进当前位置无法再次经过
use[a][b] = 1; //设置当前位置无法再次经过
way[stemp_number][0] = a;
way[stemp_number][1] = b; //添加路径
stemp_number++;
if (use[wid - 1][lon - 1] == 1) {
win = 1;
stemp = stemp_number; // (wid - 1,lon - 1)为结束点，win表示赢的胜利走到目标点，stemp记录到达目标点的步数
}
int n = 4;
while (n--) { //在当前位置尝试四个方向前进
dir = (dir + 3) % 4;
if ( win == 1)
return; //判断是否到达目标点，到达则不用继续下一步直接结束
if (dir == 0)
ssss(0, a - 1, b, stemp_number); //向上前进
if (dir == 1)
ssss(1, a, b + 1, stemp_number); //向右前进
if (dir == 2)
ssss(2, a + 1, b, stemp_number); //向下前进
if (dir == 3)
ssss(3, a, b - 1, stemp_number); //向左前进
}
}
发表于 2023-04-06 01:32:18
回复(1)
广度优先遍历，借助辅助队列和visited数组寻找单源最短路径
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#define MaxSize 100 //定义队列元素的最大个数
typedef struct point { //定义结点信息
int x;
int y;
} POINT;
typedef struct queue { //定义顺序队列
POINT point[MaxSize];
int front, rear;
} QUEUE;
//判断队列是否为空
bool IsEmpty(QUEUE q) {
if (q.rear == q.front) //队空条件
return true;
else
return false;
}
//入队
bool EnQueue(QUEUE* q, POINT point) {
if ((q->rear + 1) % MaxSize == q->front) //队满条件
return false;
memcpy(&q->point[q->rear], &point, sizeof(POINT));
q->rear = (q->rear + 1) % MaxSize;
return true;
}
//出队
bool DeQueue(QUEUE* q, POINT* point) {
if (q->rear == q->front)
return false;
memcpy(point, &q->point[q->front], sizeof(POINT));
q->front = (q->front + 1) % MaxSize;
return true;
}
int main() {
int maze[10][10] = {0};
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &maze[i][j]);
}
}
int visited[10][10] = {0}; //记录结点是否访问过
POINT father[10][10] = {0}; //记录当前结点的父亲
QUEUE Q = {{0}, 0}; //初始化队列
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < 10; ++j) {
father[i][j].x = -1; //初始化所有结点不可达
father[i][j].y = -1;
}
}
visited[0][0] = true; //初始条件
POINT u = {0, 0};
EnQueue(&Q, u);
while (!IsEmpty(Q)) { //BFS算法主过程
DeQueue(&Q, &u); //对头元素u出队
//遍历上、下、左、右邻接点
POINT local[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = 0; i < 4; i++) {
POINT w = {u.x + local[i].x, u.y + local[i].y};
if (w.x >= 0 && w.x < n && w.y >= 0 && w.y < m) { //边界
if (!visited[w.x][w.y] &&
maze[w.x][w.y] == 0) { //w为u的尚未访问的邻接顶点
memcpy(&father[w.x][w.y], &u, sizeof(POINT)); //路径应从u到w
visited[w.x][w.y] = true; //设已访问标记
EnQueue(&Q, w); //顶点w入队
}
}
}
}
//将father从最后一个结点[n-1,m-1]回溯到[0,0]，整理打印输出
POINT fater2[100] = {0};
int count = 0;
int father_x = n - 1;
int father_y = m - 1;
while (!(father_x == 0 && father_y == 0)) {
memcpy(&fater2[count], &father[father_x][father_y], sizeof(POINT));
int temp_x = father_x;
int temp_y = father_y;
father_x = father[temp_x][temp_y].x;
father_y = father[temp_x][temp_y].y;
count++;
}
for (int i = count - 1; i >= 0; i--) {
printf("(%d,%d)\n", fater2[i].x, fater2[i].y);
}
printf("(%d,%d)", n - 1, m - 1);
return 0;
}
发表于 2023-02-27 22:32:43
回复(0)
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>
#include<errno.h>
//定义一个结构体存储当前的位置坐标
typedef struct Position{
int row;
int col;
}Pos;
//////////////////////////进行栈相关代码的编写
typedef Pos STDataType;
typedef struct Stack {
STDataType* a;
int top;
int capacity;
}ST;
//定义一个全局栈，用于存储迷宫中的节点
ST Path;
void StackInit(ST* head);
void StackPush(ST* head, STDataType x);
void StackPrint(ST* head);
void StackPop(ST* head);
void StackDestroy(ST* head);
bool StackEmpty(ST* head);
void StackInit(ST* head) //栈的初始化
{
head->a = NULL;
head->top = 0; //head->top=-1
head->capacity = 0;
}
bool StackEmpty(ST* head)
{
assert(head);
return head->top == 0;//栈为空返回ture，栈为假返回false
}
void StackPush(ST* head, STDataType x) //从栈顶插入元素
{
assert(head);
if (head->top == head->capacity)
{
int newcapacity = head->top == 0 ? 4 : 2 * head->capacity;
STDataType* tmp = (STDataType*)realloc(head->a, sizeof(STDataType)*newcapacity);
if (tmp == NULL)
{
printf("%s\n",strerror(errno));
exit(-1);
}
head->a = tmp;
head->capacity = newcapacity;
}
head->a[head->top] = x;
head->top++;
}
void StackPop(ST* head) //从栈顶删除元素
{
assert(head);
//assert(head->top);
assert(!StackEmpty(head));//此语句与上面一条语句具有等效作用
head->top--;
}
STDataType StackTop(ST* head)//取栈顶元素
{
assert(head);
/*assert(head->top>0);*/
assert(!StackEmpty(head));
return (head->a)[head->top-1]; //此处只能是head->top-1,不能改变为--head->top，这样会改变top的值
}
void StackDestroy(ST* head) //销毁栈
{
assert(head);
free(head->a);
head->top = head->capacity = 0;
}
//////////////////////////
bool IstruePath(int**maze,int N,int M,Pos cur)
{
if(cur.row>=0&&cur.row<N
&&cur.col>=0&&cur.col<M
&&maze[cur.row][cur.col]==0)
return true;
else
return false;
}
bool GetMazePath(int** maze,int N,int M,Pos cur)
{
StackPush(&Path,cur);
if(cur.row==N-1&&cur.col==M-1)
return true;
//将走过的坐标标记为2
maze[cur.row][cur.col]=2;
Pos next;
//进行上、下、左、右四个方位的遍历
//上
//每次遍历上、下、左、右时都需要将cur赋给next，每次遍历的时候都会改变当前next中不同方向坐标的值
next=cur; //
next.row-=1;
if(IstruePath(maze,N,M,next))
{
if(GetMazePath(maze,N,M,next))
return true;
}
//下
next=cur;
next.row+=1;
if(IstruePath(maze,N,M,next))
{
if(GetMazePath(maze,N,M,next))
return true;
}
//左
next=cur;
next.col-=1;
if(IstruePath(maze,N,M,next))
{
if(GetMazePath(maze,N,M,next))
return true;
}
//右
next=cur;
next.col+=1;
if(IstruePath(maze,N,M,next))
{
if(GetMazePath(maze,N,M,next))
return true;
}
StackPop(&Path);
return false;
}
void PrintPath(ST* path)
{
ST tpath;
StackInit(&tpath);
while(!StackEmpty(path))
{
StackPush(&tpath,StackTop(path));
StackPop(path);
}
while(!StackEmpty(&tpath))
{
Pos pos=StackTop(&tpath);
StackPop(&tpath);
printf("(%d,%d)\n",pos.row,pos.col);
}
StackDestroy(&tpath);
}
int main() {
int N,M;
while(scanf("%d %d",&N,&M)!=EOF)
{
//开辟动态二维数组
int** maze=(int**)malloc(sizeof(int*)*N);
for(int i=0;i<N;i++)
{
maze[i]=(int*)malloc(sizeof(int)*M);
}
//进行数据的录入
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
scanf("%d",&maze[i][j]);
}
}
//Print(maze,N,M); //验证开辟数组的正确性
//进行遍历得到路径,Pos中进行存储当前位置坐标
StackInit(&Path);
Pos empty={0,0};
PrintPath(&Path);
if(GetMazePath(maze,N,M,empty))
{
PrintPath(&Path);
}
else
{
printf("The maze Path Is Not\n");
}
StackDestroy(&Path);
//释放开辟的动态二维数组
for(int i=0;i<N;i++)
{
free(maze[i]);
}
free(maze);
}
return 0;
}
发表于 2022-10-31 20:52:35
回复(1)
//如果没看懂的话，就是某B视频看 麦克老师讲算法 ，讲得挺好的
#include <stdio.h>
int m, n;//入口为（0,0）
int arr[10][10] = { {1} };//0代表空地，1代表墙
int v[10][10] = { {0} };//0代表为访问，1代表已访问
int stack[100][2] = { {0,0} };//栈，存放已走的路径
int step = 0;//存放步骤数，充当栈的指针
int flag = 0;//表示正确道路已找到，1为已找到
int dx[4] = { 0,1,0,-1 };//右，下，左，上
int dy[4] = { 1,0,-1,0 };//右，下，左，上
void push(int x1, int y1)//把步骤入栈
{
stack[step][0] = x1;
stack[step][1] = y1;
}
void dfs(int x,int y)//使用dfs的方法，找出路径
{
if (x == m-1 && y == n-1)//判断是否到达终点（m-1,n-1）
{
flag = 1;
return;
}
for (int k = 0; k < 4; k++)//判断当前点位可以走哪个方向
{
int tx, ty;
tx = x + dx[k];
ty = y + dy[k];
if (arr[tx][ty] == 0 && v[tx][ty] == 0)
{
step++;
push(tx, ty);//把下一步入栈
v[tx][ty] = 1;//标记下一步为已访问点位
dfs(tx, ty);//确认可走后，进入下一步，重复dfs
if (flag == 1)
return;
step--;
v[tx][ty] = 0;//标记释放 回溯前的点位 为 未访问点位
}
}
return;
}
/*
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
*/
int main()
{
//输入实际迷宫大小
scanf("%d %d", &m, &n);
int i = 0;
int j = 0;
//初始化最大迷宫
for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
arr[i][j] = 1;
//输入题目中的迷宫
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
scanf("%d", &arr[i][j]);
dfs(0, 0);//起始位置为(0,0)
for (int i = 0; i <= step; i++)
{
printf("(%d,%d)\n", stack[i][0], stack[i][1]);
}
return 0;
}
发表于 2022-09-09 11:24:41
回复(1)
// 参考 森林木盛木林森 这位大佬才做出来的
#include <stdio.h>
struct PATH
{
int x;
int y;
struct PATH *father;
};
int main()
{
int i, j, k, n, m, x, y, z;
scanf("%d %d", &n, &m);
int maze[n][m];
struct PATH path[n * m];
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
scanf("%d", &maze[i][j]);
maze[0][0] = 1;
k = 0;
path[k].x = 0;
path[k].y = 0;
while(1)
{
x = path[k].x;
y = path[k].y;
z = 0;
if(x >= n - 1 && y >= m - 1)
break;
if(x < n - 1 && maze[x + 1][y] == 0)
{
x++;
z = 1;
}
else if(y < m - 1 && maze[x][y + 1] == 0)
{
y++;
z = 1;
}
else if(x > 0 && maze[x - 1][y] == 0)
{
x--;
z = 1;
}
else if(y > 0 && maze[x][y - 1] == 0)
{
y--;
z = 1;
}
if(z)
{
k++;
maze[x][y] = 1;
path[k].x = x;
path[k].y = y;
}
else
{
k--;
}
}
for(i = 0; i <= k; i++)
{
printf("(%d,%d)\r\n", path[i].x, path[i].y);
}
}
发表于 2022-08-28 16:33:46
回复(0)
#include <stdio.h>
#define N 10
int sign[N][N],pos[1000][2],n,m,cnt,maze[N][N],flag;
void dfs(int x,int y)
{
pos[cnt][0]=x;pos[cnt][1]=y;cnt++;
sign[x][y]=1;
if(x==n-1&&y==m-1)
{
flag=1;
return;
}
int i,j,k;
int x_incre[4]={0,1,0,-1},y_incre[4]={1,0,-1,0};
for(k=0;k<4;k++)
{
i=x+x_incre[k];j=y+y_incre[k];
if(i>=0&&j>=0&&i<n&&j<m&&!maze[i][j]&&!sign[i][j])
{
dfs(i,j);
if(flag)
return;
}
}
sign[i][j]=0;
cnt--;
}
int main()
{
int i,j,startx=0,starty=0;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&maze[i][j]);
dfs(startx,starty);
for(i=0;i<cnt;i++)
printf("(%d,%d)\n",pos[i][0],pos[i][1]);
return 0;
} 试出来了。。。
发表于 2022-04-28 15:59:23
回复(0)
整理深度优先搜索思路如下:
while(读取m和n成功){
读取输入矩阵;
初始化出发点和堆栈;
将出发点坐标入栈;
while(当前不是终点){
设置当前点为1, 标记为已经访问;
if(往一个方向探路, 且有路)
将该方向的坐标入栈;
else
top--;
更新坐标为栈顶的值;
}
从栈底往栈顶输出坐标;
}
#include <stdio.h>
int m=0, n=0; //mark row max & column max
int x=0, y=0; //x present row, y present column
int arr[10][10];
int stack[100][2];
int top=-1;
void push(int x, int y)
{
top++;
stack[top][0] = x;
stack[top][1] = y;
}
int canMove(void) //next x & next y
{
int ret = 0;
int lastx = stack[top][0];
int lasty = stack[top][1];
if(x!=0 && arr[x-1][y] == 0){ ret+=8;} //up 8
if(x!=9 && arr[x+1][y] == 0){ ret+=4;} //down 4
if(y!=0 && arr[x][y-1] == 0){ ret+=2;} //left 2
if(y!=9 && arr[x][y+1] == 0){ ret+=1;} //right 1
return ret;
}
int main(void)
{
while(scanf("%d %d", &m, &n) != EOF){ //dfs
top=-1;
x=0;
y=0;
for(int i=0; i<10; i++){
for(int j=0; j<10; j++){
arr[i][j] = 1; //set all of the map to 1
}
}
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
scanf("%d", &arr[i][j]);
}
}
int ret;
push(0,0);
while( !(x==m-1 && y==n-1) ){
arr[x][y] = 1; //set visited
if(ret = canMove()){
if (ret&8) {push(x-1, y);} //up
else if(ret&4) {push(x+1, y);} //down
else if(ret&2) {push(x, y-1);} //left
else if(ret&1) {push(x, y+1);} //right
}else{ //no way
top--; //back to last step
}
x = stack[top][0];
y = stack[top][1];
}
for(int i=0; i<=top; i++){
printf("(%d,%d)\n", stack[i][0], stack[i][1]);
}
}
return 0;
}
发表于 2022-01-17 12:20:54
回复(0)
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
int N, M;
int visit[10][10];
void Solve_Maze(int Raw, int Column, int *p)
{
if(Raw < 0 || Raw >= N || Column < 0 || Column >= M)
return;
if((Raw == N-1) && (Column == M-1))
{
visit[Raw][Column] = 2;
return;
}
if(*(p + Raw * M + Column) == 0 && visit[Raw][Column] == 0)
{
visit[Raw][Column] = 1;
Solve_Maze(Raw-1, Column, p);//上
if(visit[Raw-1][Column] == 2)
{
visit[Raw][Column] = 2;
return;
}
Solve_Maze(Raw+1, Column, p);//下
if(visit[Raw+1][Column] == 2)
{
visit[Raw][Column] = 2;
return;
}
Solve_Maze(Raw, Column-1, p);//左
if(visit[Raw][Column-1] == 2)
{
visit[Raw][Column] = 2;
return;
}
Solve_Maze(Raw, Column+1, p);//右
if(visit[Raw][Column+1] == 2)
{
visit[Raw][Column] = 2;
return;
}
}
else
return;
}
int main()
{
while(scanf("%d%d", &N, &M) != EOF)
{
memset(visit, 0, sizeof(visit));
int maze[N][M];
int i = 0;
int j = 0;
for(i=0; i<N; i++)
for(j=0; j<M; j++)
scanf("%d", &maze[i][j]);
Solve_Maze(0, 0, *maze);
/*输出*/
i = j = 0;
while((i != N-1) || (j != M-1))
{
printf("(%d,%d)\n", i, j);
visit[i][j] = 3;//已输出
if(visit[i-1][j] == 2)
i--;
else if(visit[i+1][j] == 2)
i++;
else if(visit[i][j-1] == 2)
j--;
else if(visit[i][j+1] == 2)
j++;
}
printf("(%d,%d)\n", i, j);
}
return 0;
}
发表于 2021-08-21 15:12:47
回复(0)
问题信息
难度：
12条回答
4061收藏
100332浏览
通过挑战的用户
查看代码-
2023-03-11 16:31:38
-
2023-03-09 00:06:20
-
2023-03-05 12:23:54
-
2023-03-04 20:36:49 -
2023-03-04 13:41:15
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
