首页 > 试题广场 >

迷宫问题

[问答题]

题目标题：

迷宫问题

题目描述：

定义一个二维数组： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入描述：

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

输出描述：

左上角到右下角的最短路径，格式如样例所示。

样式输入：

0 1 0 0 0

0 1 0 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>

查看答案及解析

yyaihh

#include <iostream>
#include <vector>
using namespace std;
class Solution {
	int N, M;
	vector<vector<int>> m_maze;//迷宫矩阵
	vector<pair<int, int>> m_path_cur;//当前路径
	vector<pair<int, int>> m_path_best;//最佳路径
	void dealmaze(int i, int j) {
		m_maze[i][j] = 1;//已经走过的不能再走, 所以置1
		m_path_cur.push_back({ i, j });//记录当前节点
		if (i == N - 1 && j == M - 1) {//是否到达终点
			if (m_path_best.empty() || m_path_cur.size() < m_path_best.size()) {//选择最短路径
				m_path_best = m_path_cur;
			}
		}
		if (i - 1 >= 0 && m_maze[i - 1][j] == 0)//向上走是否可行
			dealmaze(i - 1, j);
		if (i + 1 < N && m_maze[i + 1][j] == 0)//向下走是否可行
			dealmaze(i + 1, j);
		if (j - 1 >= 0 && m_maze[i][j - 1] == 0)//向左走是否可行
			dealmaze(i, j - 1);
		if (j + 1 < M && m_maze[i][j + 1] == 0)//向右走是否可行
			dealmaze(i, j + 1);
		//不能继续走了, 要么走完了, 要么死路了, 回到上一步
		m_maze[i][j] = 0;//恢复现场，上一个位置要设为未走, 所以置0
		m_path_cur.pop_back();//当前路径退回, 所以pop
	}
public:
	vector<pair<int, int>>& maze() { 
		m_path_best.clear();
		m_path_cur.clear();
		dealmaze(0, 0);
		m_maze.clear();
		return m_path_best;
	}
	friend istream& operator>>(istream& os, Solution& s);
};
istream& operator>>(istream& os, Solution& s) {
	os >> s.N >> ***;
	***_maze.resize(s.N, vector<int>(***));
	for (auto& i : ***_maze) {
		for (auto& j : i) {
			os >> j;
		}
	}
	return os;
}
int main() {
	Solution s;
	while (cin >> s) { 
		vector<pair<int, int>>& bp = ***aze();
		for (auto i : bp) {
			cout << '<' << i.first << ',' << i.second << '>';
		}
                cout << endl;
	}
	return 0;
}

发表于 2019-12-02 10:54:30 回复(0)

LemonTree_iac

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <assert.h>

#include <memory.h>

#include <stdbool.h>

typedef struct Postion

{

int row;

int col;

}PT;

typedef PT STDataType;

typedef struct Stack

{

STDataType* a;

int top;

int capacity;

}ST;

void StackInit(ST* ps);

void StackDestroy(ST* ps);

void StackPush(ST* ps,STDataType x);

void StackPop(ST* ps);

STDataType StackTop(ST* ps);

int StackSize(ST* ps);

int StackEmpty(ST* ps);

void StackInit(ST* ps)

{

assert(ps);

ps->a = NULL;

ps->capacity = 0;

ps->top = 0;

}

void StackDestroy(ST* ps)

{

assert(ps);

free(ps->a);

ps->a = NULL;

ps->top = ps->capacity = 0;

}

void StackPush(ST* ps,STDataType x)

{

assert(ps);

if(ps->top == ps->capacity)

{

int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType)*newcapacity);

if(tmp == NULL)

{

printf("realloc fail\n");

exit(-1);

}

ps->a = tmp;

ps->capacity = newcapacity;

}

ps->a[ps->top] = x;

ps->top++;

}

void StackPop(ST* ps)

{

assert(ps);

assert(ps->top>0);

ps->top--;

}

STDataType StackTop(ST* ps)

{

assert(ps);

assert(!StackEmpty(ps));

return ps->a[ps->top - 1];

}

int StackSize(ST* ps)

{

assert(ps);

return ps->top;

}

int StackEmpty(ST* ps)

{

assert(ps);

//if(ps->top == 0)

//{

// return true;

//}

//else

//{

// return false;

//}

return ps->top == 0;

}

ST path;

////////////////////////////////////////////////////////////

void PrintMaze(int** maze,int N,int M)

{

for(int i =0;i<N;++i)

{

for(int j = 0;j<M;++j)

{

printf("%d ",maze[i][j]);

}

printf("\n");

}

//输出栈的坐标

void PrintPath(ST* ps)

{

ST rPath;

StackInit(&rPath);

while(!StackEmpty(&path))

{

StackPush(&rPath,StackTop(&path));

StackPop(&path);

}

while(!StackEmpty(&rPath))

{

PT top = StackTop(&rPath);

printf("(%d,%d)",top.row,top.col);

printf("\n");

StackPop(&rPath);

}

StackDestroy(&rPath);

}

bool isPass(int** maze,int N,int M,PT pos)

{

if(pos.row >= 0 && pos.row < N

&& pos.col >= 0 && pos.col < M

&& maze[pos.row][pos.col] == 0)

{

return true;

}

else

{

return false;

}

bool GetMazePath(int** maze,int N,int M,PT cur)

{

StackPush(&path,cur);

//如果走到出口

if(cur.row == N-1 && cur.col == M-1)

{

return true;

}

//探测cur位置的上下左右四个方向

PT next;

maze[cur.row][cur.col] = 2;//把上次循环的0填为2，防止死循环

//上

next = cur;

next.row -= 1;

if(isPass(maze,N,M,next))

{

if(GetMazePath(maze,N,M,next))

return true;

}

//下

next = cur;

next.row += 1;

if(isPass(maze,N,M,next))

{

if(GetMazePath(maze,N,M,next))

return true;

}

//左

next = cur;

next.col -= 1;

if(isPass(maze,N,M,next))

{

if(GetMazePath(maze,N,M,next))

return true;

}

//右

next = cur;

next.col += 1;

if(isPass(maze,N,M,next))

{

if(GetMazePath(maze,N,M,next))

return true;

}

StackPop(&path);

return false;

}

int main() {

int N=0,M=0;

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]);

}

//PrintMaze(maze,N,M);

StackInit(&path);

PT entry = {0,0};

if(GetMazePath(maze, N, M, entry))

{

//printf("找到通路\n");

PrintPath(&path);

}

StackDestroy(&path);

for(int i = 0;i<N;i++)

{

free(maze[i]);

}

free(maze);

}

return 0;

}

发表于 2023-05-22 22:22:15 回复(0)

bailin

回溯法+双端队列：
1.迷宫问题经典解法就是回溯
2.本题还要应用双端队列deque的原因在于：
  a)寻找最短的路径，那肯定有的路径不合适，需要将新入队的不合适节点（队尾）退出；
    用queue并不能退出队尾元素，所以queue不合适；
    用stack是能退出栈顶元素，但是结果出来后，因为遵循先入后出，要是直接打印，将
    会是从终点到起点的最短路径，与答案的顺序刚好相反，需要额外操作才能输出正确
  b)而使用双端队列就会简单很多，不合适的节点直接pop_back()即可。输出结果时仅需
    push_front()即可。既有栈的特点，又有队的特点。何乐而不为？
该题思路：
1.四个方向，上下左右提前定义好
2.接下来就是回溯常规套路
  a）到达终点，与现有结果比长短，短则更新，长则抛弃
  b）四个方向去继续回溯，要进行剪枝，更新标志数组vis,不走重复道路
3.得到结果，打印即可
#include <iostream>
#include <vector>
#include <deque>
#include <string>
#pragma warning(disable:4996)
using namespace std;
 
class Solution {
public:
    void ShortPath(const vector<vector<int>>& board) {
        m = board.size();
        n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        visited[0][0] = true;
        deque<string> dq;//定义双端队列，不合适的路径可以从队尾删除
        dq.push_back("(0,0)");//将起点加入
        BackTrack(board, 0, 0, dq, visited);//回溯解决
 
        while (!ans.empty()) {
            cout << ans.front() << endl;
            ans.pop_front();
        }
    }
private:
    void BackTrack(const vector<vector<int>>& board, int x, int y, deque<string>& dq, vector<vector<bool>>& vis) {
        if (x == m - 1 && y == n - 1) {//到达终点
            if (ans.empty() || dq.size() < ans.size())//结果集为空；目前最短
                ans = dq;
            return;
        }
        for (int i = 0; i < 4; ++i) {//4个方向探索
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx >= m || ny >= n || nx < 0 || ny < 0 || board[nx][ny] || vis[nx][ny])
                continue;//索引越界;障碍;走过的路径
            vis[nx][ny] = true;//更新标志
            char tmp[64] = { 0 };
            sprintf(tmp, "(%d,%d)", nx, ny);
            dq.push_back(string(tmp));//加入新坐标
            BackTrack(board, nx, ny, dq, vis);//深入探索
            dq.pop_back();//回退
        }
    }
private:
    int m;
    int n;
    int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
    deque<string> ans;
};
int main() {
    int n, m;
    Solution S;
    while (cin >> m >> n) {
        vector<vector<int>> board(m, vector<int>(n));
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                cin >> board[i][j];
        S.ShortPath(board);
    }
    return 0;
}

编辑于 2021-06-19 19:03:20 回复(0)

Ares.Luo

#include <cstdio>
#include <cstring>
#include <queue>
#define INF 0x7F7F7F7F
using namespace std;
struct Point
{
    int x, y;
} now, nxt, opt[105];
int mapp[15][15], fx[8] = { 1, 0, -1, 0, 0, -1, 0, 1 };
int main()
{
    int i, j, tmp;
    for (i = 1; i <= 5; ++i)
        for (j = 1; j <= 5; ++j)
        {
            scanf("%d", &tmp);
            if (!tmp)
                mapp[i][j] = INF;
        }
    queue<struct Point> q;
    now.y = now.x = 1;
    q.push(now);
    mapp[1][1] = 2;
    while (!q.empty())
    {
        now = q.front();
        q.pop();
        tmp = mapp[now.y][now.x] + 1;
        for (i = 0; i < 8; i += 2)
        {
            nxt.y = now.y + fx[i];
            nxt.x = now.x + fx[i + 1];
            if (mapp[nxt.y][nxt.x] == INF)
            {
                mapp[nxt.y][nxt.x] = tmp;
                q.push(nxt);
            }
        }
    }
    now.y = now.x = 5;
    q.push(opt[0] = now);
    j = 1;
    while (!q.empty())
    {
        now = q.front();
        q.pop();
        tmp = mapp[now.y][now.x] - 1;
        for (i = 0; i < 8; i += 2)
        {
            nxt.y = now.y + fx[i];
            nxt.x = now.x + fx[i + 1];
            if (mapp[nxt.y][nxt.x] == tmp)
            {
                opt[j++] = nxt;
                q.push(nxt);
                break;
            }
        }
    }
    for (i = j - 1; i>=0; i--)
        printf("(%d, %d)\n", opt[i].y - 1, opt[i].x - 1);
    return 0;
}

发表于 2019-03-20 16:34:42 回复(0)

阿奻_

#include<stdio.h>

int map[5][5];

int dx[4]={1,-1,0,0};

int dy[4]={0,0,-1,1};

int front=0,rear=1;

struct node{

int x,y,pre;

}q[5*5];

void print(int i)// 输出过程

{

if(q[i].pre!=-1)

{

print(q[i].pre);

printf("<%d,%d>",q[i].x,q[i].y);

}

void bfs(int x1,int y1)// 广搜

{

q[front].x=x1;

q[front].y=y1;

q[front].pre=-1;

while(front<rear)// 当队列不空

{

for(int i=0;i<4;i++)// 搜索可达的路径

{

int a=dx[i]+q[front].x;

int b=dy[i]+q[front].y;

if(a<0||a>=5||b<0||b>=5||map[a][b])// 是否在迷宫内，是否可行

continue;

else

{

map[a][b]=1; // 走过的路做标记

q[rear].x=a;

q[rear].y=b;

q[rear].pre=front;

rear++; // 入队

}

if(a==4&&b==4) print(front);

}

front++;// 出队

}

int main()

{

int i,j;

for(i=0;i<5;i++)

for(j=0;j<5;j++)

scanf("%d",&map[i][j]);

printf("<0,0>");

bfs(0,0);

printf("<4,4>");

return 0;

}

发表于 2017-05-15 00:23:23 回复(0)

提交观点

问题信息

C++

上传者：阿奻_

难度：

5条回答 12收藏 4015浏览

迷宫问题

问题信息

热门推荐

相关试题