本文主要是介绍炫酷迷宫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
小希现在需要你构建一个简单的方格图迷宫，'.'作为路，'x'作为障碍。
要求方格图大小为N*M，起点到终点的最短距离恰好为K。
方格图为四连通，即对于任何一个格子只能上下左右走，相邻格子距离为1，不能走出边界。
【输入描述】
一行给出三个整数N，M，K，分别表示需要的方格图的行数，列数和起点到终点的最短距离。
1≤N,M≤1000
1≤K≤N∗M且保证可以构造出至少一张图使得最短距离为K。
【输出描述】
第一行给出起点的坐标xs,ys，坐标从1开始。
第二行给出终点的坐标xt,yt，
第三行开始输出N*M的方格图，N行，M列。
如果有多种方案，输出任意一种即可。
【样例】
示例1
输入
3 3 5
输出
1 2
3 1
x..
xx.
...示例2
输入
4 2 3
输出
4 1
2 2
xx
x.
..
.x示例3
输入
1 10 9
输出
1 1
1 10
..........
思路：
本质上是一个图的搜索，只不过是从传统的搜索路径变为先构造图再进行搜索
【源代码】
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define PI acos(-1.0)
#define E 1e-6
#define INF 0x3f3f3f3f
#define N 3001
#define LL long long
const int MOD=1e9+7;
using namespace std;
struct Edge{int x,y;int num;Edge(){}Edge(int x,int y,int num):x(x),y(y),num(num){}
};
int n,m,k;
char G1[N][N],G2[N][N];
bool vis[N][N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
bool judge(int x,int y){return x>=1 && x<=n && y>=1 && y<=m && G1[x][y]=='.' && !vis[x][y];
}
void bfs(){vis[1][1]=true;queue<Edge> Q;Q.push(Edge(1,1,0));while(!Q.empty()){Edge temp=Q.front();Q.pop();if(temp.num==k){cout<<temp.x<<" "<<temp.y<<endl;return;}for(int i=0;i<4;i++){int nx=temp.x+dx[i];int ny=temp.y+dy[i];int num=temp.num+1;Edge next=Edge(nx,ny,num);if(judge(nx,ny)){Q.push(next);vis[nx][ny]=true;}}}
}
int main(){cin>>n>>m>>k;int res=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(i%2){G1[i][j]='.';res++;}elseG1[i][j]='x';}}for(int i=2;i<=n;i+=4){G1[i][m]='.';res++;}for(int i=4;i<=n;i+=4){G1[i][1]='.';res++;}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(i%2){G2[j][i]='.';res--;}elseG2[j][i]='x';}}for(int i=2;i<=m;i+=4){G2[n][i]='.';res--;}for(int i=4;i<=m;i+=4){G2[1][i]='.';res--;}if(res<0)for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)G1[i][j]=G2[i][j];cout<<"1 1"<<endl;bfs();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cout<<G1[i][j];cout<<endl;}return 0;
}
这篇关于炫酷迷宫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
