DFS遍历每条路并回溯,用vector存放坐标
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
vector<PII> v;
const int N = 20;
int mp[N][N];
int vis[N][N];
int n,m;
int sx,sy;
int x2,y2;
int dx[] = {0,-1,0,1};
int dy[] = {-1,0,1,0};
int flag = 0;
void dfs(int x,int y){
vis[x][y] = 1;
if (x == x2 && y == y2) {
flag = 1;
printf("(%d,%d)",sx,sy);
for (int i = 1; i < v.size() - 1; ++i){
printf("->(%d,%d)",v[i].first,v[i].second);
}
printf("->(%d,%d)\n",x2,y2);
}
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (vis[nx][ny]) continue;
if (mp[nx][ny] == 0) continue;
vis[nx][ny] = 1;
v.push_back({nx,ny});
dfs(nx,ny);
v.pop_back();
vis[nx][ny] = 0;
}
return;
}
int main(){
scanf("%d %d",&n,&m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> mp[i][j];
}
}
scanf("%d %d",&sx,&sy);
scanf("%d %d",&x2,&y2);
v.push_back({sx,sy});
dfs(sx,sy);
if(flag == 0) printf("-1\n");
return 0;
}
0 回复
0 转发
0 喜欢
2 阅读



