问2 求教！关于迷宫问题，在线等，急！
2024-03-27 20:40:57
发布于：广东
38阅读
0回复
0点赞
【问题2】
迷宫问题
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述
设有一个N*N(2<=N<10)方格的迷宫，入口和出口分别在左上角和右上角。
迷宫格子中分别放0和1，0表示可通，1表示不能，入口和出口处肯定是0。
迷宫走的规则如下所示：即从某点开始，有八个方向可走，前进方格中数
字为0时表示可通过，为1时表示不可通过，要另找路径。找出所有从入口（左上角）
到出口（右上角）的路径(不能重复)，输出路径总数，如果无法到达，则输出0。
输入
第一行输入n，表示n行n列的迷宫
接下来有n行，每行n个数，分别用1或0表示能否通过
输出
输出路径数
样例输入
3
0 0 0
0 1 1
1 0 0
样例输出
2
迷宫问题例题分析图：
迷宫问题方向分析图：
我的代码：
#include<bits/stdc++.h>
using namespace std;
int sr[300],mg[15][15],j,t,a,b,cnt,dx[9]={0,-1,-1,-1,0,+1,+1,+1,0},dy[9]={0,-1,0,+1,+1,+1,0,-1,-1},n;
void hs(int x,int y,int n)
{
if(x==1&&y==n)
{
cnt++;
return;
}
for(int i=1;i<=8;i++)
{
int xx,yy;
xx=x+dx[i];
yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&mg[xx][yy]==0)
{
mg[xx][yy]=1;
hs(xx,yy,n);
mg[xx][yy]=0;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n*n;i++)
{
cin>>sr[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
t++;
mg[i][j]=sr[t];
}
}
mg[1][1]=1;//起点（左上角）
mg[1][n]=1;//终点（右上角）
hs(1,1,n);
cout<<cnt;
}
（注：只得了20分。。。。。。。到底哪里错了呀😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭）
2024.3.23 11:55:40这题成功在Macw07的帮助下AC了！！！！！！！！！！！1
Macw修改后的代码：
#include<iostream>
using namespace std;
int map[15][15];
int sr[300],mg[15][15],j,t,a,b,cnt;
int dx[9]={0,-1,-1,-1,0,+1,+1,+1,0};
int dy[9]={0,-1,0,+1,+1,+1,0,-1,-1},n;
void hs(int x,int y,int n)
{
if(x==1&&y==n)
{
cnt++;
return;
}
for(int i=1;i<=8;i++)
{
int xx,yy;
xx=x+dx[i];
yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&mg[xx][yy]==0&&map[xx][yy]==0)
{
mg[xx][yy]=1;
hs(xx,yy,n);
mg[xx][yy]=0;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) {
cin >> map[i][j];
}
}
mg[1][1] = 1;
// map[1][1]=1;//起点（左上角）
// map[1][n]=1;//终点（右上角）
hs(1,1,n);
cout<<cnt;
}
大佬，请感受我的膜拜🧎♀️还有，全排列那道题AC了，不要不帮我嘛🙏
全部评论 3
找到问题所在了，你的mg数组既记录一个节点是否被访问过，又记录了地图的0和1属性。这导致回溯的时候会出问题。一个解决办法是把mg数组分成两个数组map和mg，分别记录地图和是否访问过节点。修改后的：https://www.luogu.com.cn/paste/2pph2drt。
2024-03-23 来自
2
有帮助，赞一个