1238 走迷宫
em
做完这个题去提交作业
这个题应该又是一个图论
我最烦这样的路线输出题了,我服了
不过这个题就是一个搜索,简单的不能再简单的搜索,就是输出有点难
我试试
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;//搜索的顺序 左上右下
int n,m;
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
int flag;
int startx,starty,endx,endy;
int book[200][200];//标记数组
struct st
{
int x;
int y;//记录横纵坐标
}b[200];
void print(int n)
{
flag=1;//有路
for(int i=1;i<n;i++)
{
printf("(%d,%d)->",b[i].x,b[i].y);
}
printf("(%d,%d)\n",b[n].x,b[n].y);
}
void dfs(int n,int startx,int starty,int endx,int endy)
{
for(int i=0;i<=3;i++)//方位
{
book[startx][starty]=0;
startx+=dx[i];
starty+=dy[i];
if(book[startx][starty]==1)
{
b[n].x=startx;
b[n].y=starty;//记录路径的数组
if(startx==endx&&starty==endy) print(n);//搜索道了
else dfs(n+1,startx,starty,endx,endy);//接着往下搜索
}
startx-=dx[i];
starty-=dy[i];
book[startx][starty]=1;//回溯
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>book[i][j];//只有1 0
}
}
cin>>startx>>starty>>endx>>endy;
b[1].x=startx,b[1].y=starty;
dfs(2,startx,starty,endx,endy);//第一个点已经有了,所以从2开始
//记录的是坐标
if(flag==0) cout<<-1<<endl;//没有路
return 0;
}