返回题解分享
讨论 / 题解分享/ 帖子详情

走迷宫输出路径 - 题解

//模板
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f

//移动向量
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};

//创建迷宫
int a[42][42];

//起点终点
pair<int , int> Start;
pair<int , int> End;

//迷宫大小
int n,m;

//方案总数
int flag = 0;

//第一次
int diyici = 1;

//该点是否来过
bool coming[42][42];

//路线
vector<pair<int , int> > Path;

void dfs(pair<int , int> now)
{
if(now == End)
{
Path.push_back(End);

for(int i = 0 ; i < Path.size() - 1 ; i++)
{
cout << "(" << Path[i].first + 1 << "," << Path[i].second + 1 << ")" << "->";
}

cout << "(" << Path[Path.size() - 1].first + 1<< "," << Path[Path.size() - 1].second + 1 << ")" << endl;

flag = 1;

Path.pop_back();
coming[now.first][now.second] = 0;
}


for(int i = 0 ; i < 4 ; i++)
{
Path.push_back(now);

int nex = now.second + dx[i] , ney = now.first + dy[i];
if(nex >= 0 && nex < m && ney >= 0 && ney < n /位置可取/ && coming[ney][nex] != 1 /下一个位置未去过/ && a[ney][nex] == 1 /此路可通/)
{
coming[now.first][now.second] = 1;
coming[ney][nex] = 1;

dfs({ney,nex});

//回溯
coming[now.first][now.second] = 0;
coming[ney][nex] = 0;
}

Path.pop_back();
}

return;
}

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

memset(coming , 0 , sizeof(coming) );
memset(a , 0 , sizeof(a));

//初始化迷宫
cin >> n >> m;
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < m ; j++)
{
cin >> a[i][j];
}
}

//起点和终点
int First,Second;

//(y,x)
//first -- y
//second -- x

//起点
cin >> First >> Second;
Start.first = First - 1;
Start.second = Second - 1;

//终点
cin >> First >> Second;
End.first = First - 1; // y
End.second = Second - 1; // x

/
r(int i = 0 ; i < n ; i++)
{ 1 =
for(int j = 0 ; j < m ; j++)
{ 1 =
cout << a[i][j];
}
}

cout << "(" << Start.first << "," << Start.second << ")" ;
cout << "(" << End.first << "," << End.second << ")" ;

auto temp = make_pair(1,1);

if(Start == temp)
{
cout << endl << "Right compare" << endl;
}
/

dfs(Start);

if(flag == 0)
{
cout << "-1";
}

return 0;
}
0 回复 0 转发 0 喜欢 7 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!