プログラミングトレーニング-迷路のすべての解を出力します(迷路の最短ではありません)
28411 ワード
タイトルの説明
以前BFSで迷路の最短ルートを解決する問題を書いたことがありますが、この文章はもう一つの問題で、それは迷路を出力するすべての可能な経路です.サンプルの入出力を直接見ると、問題の意味がわかります.
サンプル入力1
3代表迷宮は3×\times × 3の、
サンプル出力1
明らかにこの迷路には1つの経路しかなく、上記は起点の次のステップから始まるすべての点座標を出力している.
サンプル入力2
サンプル出力2
この迷宮問題には4つの解がある.
データ規定
指定入力位置座標は必ず(0,0)、迷宮は正方形で、最大規模は100を超えない×\times × 100.(迷路を長方形にしたいなら、次のプログラムに長さや幅の変数を加えればいい)
アルゴリズム#アルゴリズム#
コアアルゴリズムは疑似コードで表される.
使用するデータ構造および補助機能の構造は、言うまでもなく、参照コードを参照してください.
リファレンスコード
開拓(騎士遊歴問題)
一つの問題を広げます:騎士の遊歴の問題、碁盤の規模を入力して、騎士の初期の座標を入力して、騎士は“日”の字形を歩くしかなくて、1つの繰り返してすべての格子の経路を歩くことができないことを求めます.
迷宮問題を用いたアルゴリズム思想でもあるが,このアルゴリズムは騎士遊歴問題に用いられ,複雑度がかなり高く,プログラムを実行する際に肉眼で見るのが遅い.ネット上には貪欲法を組み合わせた解法もあり、それは騎士の遊歴問題を解く合理的な解法であるべきで、ここで私は迷宮問題のために開拓して強固にしただけだ.
参照コード:
以前BFSで迷路の最短ルートを解決する問題を書いたことがありますが、この文章はもう一つの問題で、それは迷路を出力するすべての可能な経路です.サンプルの入出力を直接見ると、問題の意味がわかります.
サンプル入力1
3
s..
*.*
..e
3代表迷宮は3×\times × 3の、
s
は起点を表し、e
は終点を表し、.
は路を表し、'*'
は壁を表す.サンプル出力1
(0,1)(1,1)(2,1)(2,2)
明らかにこの迷路には1つの経路しかなく、上記は起点の次のステップから始まるすべての点座標を出力している.
サンプル入力2
3
s..
*..
..e
サンプル出力2
(0,1)(0,2)(1,2)(2,2)
(0,1)(0,2)(1,2)(1,1)(2,1)(2,2)
(0,1)(1,1)(1,2)(2,2)
(0,1)(1,1)(2,1)(2,2)
この迷宮問題には4つの解がある.
データ規定
指定入力位置座標は必ず(0,0)、迷宮は正方形で、最大規模は100を超えない×\times × 100.(迷路を長方形にしたいなら、次のプログラムに長さや幅の変数を加えればいい)
アルゴリズム#アルゴリズム#
コアアルゴリズムは疑似コードで表される.
// (x,y)
findPath(int x, int y){
(x,y) ;
if (x,y) {
;
;
}
else{
for (x,y) A{
A, A ;
findPath(A ); //
A ;
}
}
(x,y) ;
}
使用するデータ構造および補助機能の構造は、言うまでもなく、参照コードを参照してください.
リファレンスコード
#include
#define maxn 105
int flag[maxn][maxn]; //
char map[maxn][maxn]; //
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
// , c++, pair
int path_x[maxn*maxn]; //
int path_y[maxn*maxn]; //
int length; //
int n; //
void findPath(int x, int y){
flag[x][y] = 1;
if(map[x][y]=='e'){
for(int i = 0;i < length;i++){
printf("(%d,%d)", path_x[i], path_y[i]);
}
printf("
");
}
else{
for(int i = 0;i < 4;i++){
if(x+dx[i]>=0&&x+dx[i]<n&&y+dy[i]>=0&&y+dy[i]<n
&&flag[x+dx[i]][y+dy[i]]==0&&map[x+dx[i]][y+dy[i]]!='*'){
path_x[length] = x + dx[i];
path_y[length++] = y + dy[i];
findPath(x+dx[i], y+dy[i]);
length--;
}
}
}
flag[x][y] = 0;
}
int main(){
while(scanf("%d", &n)==1){
getchar();
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
scanf("%c", &map[i][j]);
}
getchar();
}
findPath(0, 0);
}
return 0;
}
開拓(騎士遊歴問題)
一つの問題を広げます:騎士の遊歴の問題、碁盤の規模を入力して、騎士の初期の座標を入力して、騎士は“日”の字形を歩くしかなくて、1つの繰り返してすべての格子の経路を歩くことができないことを求めます.
迷宮問題を用いたアルゴリズム思想でもあるが,このアルゴリズムは騎士遊歴問題に用いられ,複雑度がかなり高く,プログラムを実行する際に肉眼で見るのが遅い.ネット上には貪欲法を組み合わせた解法もあり、それは騎士の遊歴問題を解く合理的な解法であるべきで、ここで私は迷宮問題のために開拓して強固にしただけだ.
参照コード:
// , ,
// , ( https://blog.csdn.net/wqk1014/article/details/8283325?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task)
#include
#define maxn 105
int flag[maxn][maxn];
int end = 0; //
int count = 0; //
int n; //
int path_x[maxn+1], path_y[maxn+1];
int start_x, start_y; //
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
void findPath(int x, int y){
printf(" ,count=%d
", count);
flag[x][y] = 1;
if(count == n * n){
end = 1; // ,
for(int i = 0;i < count;i++){
printf("(%d,%d)", path_x[i], path_y[i]);
}
printf("
");
}
else{
for(int i = 0; i < 8;i++){
if(x+dx[i]>=0&&x+dx[i]<n&&y+dy[i]>=0&&y+dy[i]<n
&&flag[x+dx[i]][y+dy[i]]==0){
path_x[count] = x + dx[i];
path_y[count++] = y + dy[i];
if(end == 0){
findPath(x+dx[i], y+dy[i]);
}
count--;
}
}
}
flag[x][y] = 0;
}
int main(){
while(scanf("%d", &n)==1){
scanf("%d %d", &start_x, &start_y);
count = 0;
end = 0;
path_x[count] = start_x;
path_y[count++] = start_y;
findPath(start_x, start_y);
}
return 0;
}