外网平面设计网站,建设规划,怎么建设外贸网站,长春seo优化迷宫问题的最短路#xff0c;加最小字典序 迷宫文件maze.txt传送门 作者写的2019年B组蓝桥杯解集 . . .
DFS的版本
#includeiostream
#includecstring
using namespace std;
const int ax[4]{0,0,1,-1};
const int ay[4]{1,-1,0,0};
const char dir[5]{R,L…迷宫问题的最短路加最小字典序 迷宫文件maze.txt传送门 作者写的2019年B组蓝桥杯解集 . . .
DFS的版本
#includeiostream
#includecstring
using namespace std;
const int ax[4]{0,0,1,-1};
const int ay[4]{1,-1,0,0};
const char dir[5]{R,L,D,U};
int maze[60][60],mins[60][60];
char a[2000];
int best;
string ans;
bool judge(int x,int y) {//判断这个点是否越界是否走过。if(x0x30y0y50!maze[x][y])return true;return false;
}
void dfs(int x,int y,int pos) {if(posbest)return ;if(x30y50) {string temp;for(int i1;ipos;i)tempa[i];if(posbest) {//是最短的路anstemp;bestpos;}else if(posbesttempans) anstemp;//在实现路时最短的同时保证字典序最小。return ;}for(int i0;i4;i) {int tempxxax[i];int tempyyay[i];if(judge(tempx,tempy)pos1mins[tempx][tempy]) {maze[tempx][tempy]1;mins[tempx][tempy]pos1;a[pos]dir[i];dfs(tempx,tempy,pos1);maze[tempx][tempy]0;//回溯找短的路或者时字典序最小的。}}
}
int main()
{freopen(D:\\MY\\ce.txt,r,stdin);memset(mins,1,sizeof(mins));best128;for(int i1;i30;i)for(int j1;j50;j) {char t;cint;maze[i][j]t-0; }maze[1][1]1;dfs(1,1,1);coutansendl;return 0;
}其中最重要的就是数组mins,这里记录了从起始位置到这里的最短步数 l l当这个点在可以到达终点的路径上时也有可能有多种方式到这个点所以一点更要保证时最小的步数到可以到达终点的路径上的点。 . . . BFS版本
#includeiostream
#includecstring
#includequeue
const int ax[4]{1,0,0,-1};
const int ay[4]{0,-1,1,0};
const char dir[5]{D,L,R,U};
int maze[40][60];
using namespace std;
struct point {int x,y;string ans;point(int a,int b,string c):x(a),y(b),ans(c){}
};
bool judge(int x,int y) {if(x0x30y0y50!maze[x][y])return true;return false;
}
void bfs() {queuepointans;ans.push(point(1,1,));maze[1][1]1;while(!ans.empty()) {point tempans.front();ans.pop();if(temp.x30temp.y50) {couttemp.ansendl;return ;}for(int i0;i4;i) {int tempxtemp.xax[i];int tempytemp.yay[i];if(judge(tempx,tempy)) {maze[tempx][tempy]1;ans.push(point(tempx,tempy,temp.ansdir[i]));}}}
}
int main() {freopen(D:\\MY\\ce.txt,r,stdin);for(int i1;i30;i)for(int j1;j50;j) {char t;cint;maze[i][j]t-0; }bfs();return 0;
}这里就不用考虑回溯的问题不用考虑是不是最短路的问题但是可能有一个是不是字典序最小需要考虑 . 于是我把这里的dir方向数组设置成了D L R U的顺序保证了在步数最小的前提下最小字典序一定会最早出现。
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR * ** ** * 还有一点要注意的就是我这里 用的是int数组存地图地图之间没有空格一定要先用char读取或者直接用char数组表示地图。 . 就因为这个我抑郁了好久,一直不知道哪里错了。
