//模板
#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;
}
#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 阅读



