炫酷迷宫(C++)
题目描述
小希现在需要你构建一个简单的方格图迷宫,’.'作为路,'x’作为障碍。
要求方格图大小为N*M,起点到终点的最短距离恰好为K。
方格图为四连通,即对于任何一个格子只能上下左右走,相邻格子距离为1,不能走出边界。
输入描述:
一行给出三个整数N,M,K,分别表示需要的方格图的行数,列数和起点到终点的最短距离。
1≤N,M≤1000
1≤K≤N∗M
且保证可以构造出至少一张图使得最短距离为K。
输出描述:
第一行给出起点的坐标,坐标从1开始。
第二行给出终点的坐标,
第三行开始输出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
..........
题目思路:
比如4*4,K=10的时候,很容易构造出:
....
xxx.
.xx.
....
于是得到了一种绕圈的想法。
但是在比如5*2,K=7中,绕圈法又遇到了阻碍,不如直走换边法,即
.x...
...x.
将这两种方法合并起来,即可以得到一种看起来还不错的解法。
如果能达到和以上算法同等优秀,就可以AC。
解题代码:
#include <iostream>
using namespace std;
char Map[1005][1005];
int main()
{
std::ios::sync_with_stdio(false);//加速
int N,M,K;//方格图的行数,列数和起点到终点的最短距离
cin >> N >> M >> K;
int startx=1,starty=1,endx=1,endy=1;//先假设起始点和终止点的坐标都为(1,1)
//先把整个方格图迷宫全部放上'x'障碍
int i,j;
for(i=1;i<=N;++i)
for(j=1;j<=M;++j)
Map[i][j]='x';
Map[endx][endy]='.';//把终止点(1,1)放上'.'路,因为终止点一定是路的位置
if( N==1 )//方格图迷宫只有1行的情况
for(j=2;j<=K+1;++j)//只能横着走
{
Map[1][j]='.';//把障碍'x'变为路'.'
endy++;//终止点所处的列数加1
}
else if( M==1 )//方格图迷宫只有1列的情况
for(i=2;i<=K+1;++i)//只能竖着走
{
Map[i][1]='.';//把障碍'x'变为路'.'
endx++;//终止点所处的行数加1
}
else if( N==2 )//方格图迷宫只有2行的情况
while(K)//直走换边法
{
if(K) endx++,K--,Map[endx][endy]='.';
if(K) endy++,K--,Map[endx][endy]='.';
if(K) endy++,K--,Map[endx][endy]='.';
if(K) endx--,K--,Map[endx][endy]='.';
if(K) endy++,K--,Map[endx][endy]='.';
if(K) endy++,K--,Map[endx][endy]='.';
}
else if( M==2 )//方格图迷宫只有2列的情况
while(K)//直走换边法
{
if(K) endy++,K--,Map[endx][endy]='.';
if(K) endx++,K--,Map[endx][endy]='.';
if(K) endx++,K--,Map[endx][endy]='.';
if(K) endy--,K--,Map[endx][endy]='.';
if(K) endx++,K--,Map[endx][endy]='.';
if(K) endx++,K--,Map[endx][endy]='.';
}
else
{
if( (N/2)*(M-1)<=(M/2)*(N-1) )
{
while(K)
{
while( endy<M && K ) endy++,K--,Map[endx][endy]='.';//绕圈
if(K) endx++,K--,Map[endx][endy]='.';//直走换边法
if(K) endx++,K--,Map[endx][endy]='.';//直走换边法
while( endy>1 && K ) endy--,K--,Map[endx][endy]='.';//绕圈
if(K) endx++,K--,Map[endx][endy]='.';//直走换边法
if(K) endx++,K--,Map[endx][endy]='.';//直走换边法
}
}
else
{
while(K)
{
while( endx<N && K ) endx++,K--,Map[endx][endy]='.';//绕圈
if(K) endy++,K--,Map[endx][endy]='.';//直走换边法
if(K) endy++,K--,Map[endx][endy]='.';//直走换边法
while( endx>1 && K ) endx--,K--,Map[endx][endy]='.';//绕圈
if(K) endy++,K--,Map[endx][endy]='.';//直走换边法
if(K) endy++,K--,Map[endx][endy]='.';//直走换边法
}
}
}
cout << startx << " " << starty << endl;
cout << endx << " " << endy << endl;
for(i=1;i<=N;++i)
{
for(j=1;j<=M;++j)
{
cout << Map[i][j];
}
cout << endl;
}
}