10分dfs求调.....
  • 板块P1238 走迷宫
  • 楼主hangv
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/30 13:01
  • 上次更新2024/3/30 15:32:48
查看原帖
10分dfs求调.....
485821
hangv楼主2024/3/30 13:01
#include<bits/stdc++.h>
using namespace std;
const int N = 1000 + 5; 
const int M = 50000 + 5;
int c = 0;//步数 
bool f = 0;
int n, m;
int sx, sy;//起点 
int fx, fy;//终点 
int mp[N][N];
bool vis[N][N];
int dx[4] = {-1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int ddx[M], ddy[M]; //存储步骤 
void dfs(int nx,int ny){
	if (nx == fx && ny == fy) {//到终点 
		f = 1;
		cout<<"(" << sx <<","<< sy << ")" << "->";
		for(int i = 0; i < c; i ++)
			cout<< "(" << ddx[i] <<","<< ddy[i] << ")" <<"->";
		cout<<"(" << fx <<","<< fy << ")" << endl;
		return;
	}
	for(int i = 0; i < 4; i ++){
		int vx = nx + dx[i], vy = ny + dy[i];//走 
		if(vx <= 0 || vx > n || vy <= 0 || vy > m)continue;
		if(vis[vx][vy] == 1 || mp[vx][vy] == 0)continue;
		vis[vx][vy] = 1;
		ddx[c] = vx;
		ddy[c] = vy;
		c ++;
		dfs(vx, vy);
		vis[vx][vy] = 0;
		c --;//回溯减步 
	}
}
int main(){
	cin>> n >> m; 
	for(int i = 1; i <= n; i ++)
		 for(int j = 1; j <= m; j++)
		 	cin>> mp[i][j];
	cin >> sx >> sy >> fx >> fy;
	vis[sx][sy] = 1;
	dfs(sx, sy);
	if(f == 0) cout<< "-1";
	return 0;
}
2024/3/30 13:01
加载中...