dfs 10分求调
  • 板块P1238 走迷宫
  • 楼主KukCair
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/30 13:06
  • 上次更新2024/3/30 15:39:56
查看原帖
dfs 10分求调
767449
KukCair楼主2024/3/30 13:06
#include <bits/stdc++.h>
using namespace std;
struct node{
	int x, y;
}p[50005];
int m, n, sx, sy, ex, ey;
bool fl;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
bool mp[105][105], f[105][105];
void dfs(int step, int x, int y){
	if(x == ex && y == ey){
		for(int i = 0; i < step; i++)
			printf("(%d,%d)->", p[i].x, p[i].y);
		printf("(%d,%d)\n", ex, ey);
		fl = 1;
		return;
	}
	for(int i = 0; i <= 3; i++){
		int nx = x + dx[i], ny = y + dy[i];
		if(nx > m || nx < 1 || ny > n || ny < 1) continue;
		if(f[nx][ny] || !mp[nx][ny]) continue;
		f[x][y] = 1;
		p[step] = {x, y};
		dfs(step + 1, nx, ny);
		f[x][y] = 0;
	}
}
int main(){
	cin >> m >> n;
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n; j++)
			cin >> mp[i][j];
	cin >> sx >> sy >> ex >> ey;
	dfs(0, sx, sy);
	if(!fl) cout << -1;
	return 0;
}
2024/3/30 13:06
加载中...