C++検索と遡及アルゴリズムの迷宮問題
1382 ワード
迷宮問題:一つの迷宮はR行C列の格子からなり、ある格子には障害物があり、歩けない.ある格子は空き地で、歩いてもいいです.を表示します.迷路を与えて、左上隅から右下隅まで歩くには少なくともどのくらいのステップが必要ですか(データは必ず行けることを保証します).水平方向または垂直方向にしか歩けず、斜めには歩けない.R、C、ラビリンスを入力し、すべてのパスを出力します.
コードは次のとおりです.
コードは次のとおりです.
#include
#include
#include
using namespace std;
int r,c;
int num1[101],num2[101],total; //
int wayr[4]={0,0,1,-1},wayc[4]={1,-1,0,0}; //
bool mark[101][101]; //
char maze[101][101]; //
bool check(int x,int y) //
{
if(x<=0||y<=0||x>r||y>c) return false;
return true;
}
void print() //
{
printf("(1,1)");
for(int i=1;i<=total;i++)
printf("->(%d,%d)",num1[i],num2[i]);
printf("
");
}
void search(int x,int y) // ，
{
for(int i=0;i<4;i++)
if(!mark[x+wayr[i]][y+wayc[i]]&&check(x+wayr[i],y+wayc[i])&&maze[x+wayr[i]][y+wayc[i]]=='.') //
{
x+=wayr[i];
y+=wayc[i];
total++;
num1[total]=x;
num2[total]=y;
mark[x][y]=true;
if(x==r&&y==c) print(); //
search(x,y); //
mark[x][y]=false; //
total--;
x-=wayr[i];
y-=wayc[i];
}
}
int main()
{
scanf("%d%d",&r,&c);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
cin>>maze[i][j];
mark[1][1]=true; //
search(1,1);
return 0;
}