7 条题解
-
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;
}
信息
- ID
- 84
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 776
- 已通过
- 118
- 上传者