dfs,蒟蒻求调
  • 板块P1238 走迷宫
  • 楼主isop
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/25 11:27
  • 上次更新2024/7/25 13:07:18
查看原帖
dfs,蒟蒻求调
1071516
isop楼主2024/7/25 11:27
//x轴竖直向下,y轴水平向右
#include<bits/stdc++.h>
using namespace std;

int m,n,sx,sy,fx,fy,a,b,tem;//tem路径节点数 
int g[15][15];
int dx[4]={-1,0,1,0};//方向数组
int dy[4]={0,1,0,-1}; 
bool flag=false;
vector<pair<int,int>>p;//存路径

inline void print(int w)//输出路径
{
	for(int i=0;i<w-1;i++)
	{
		cout<<"("<<get<0>(p[i])<<","<<get<1>(p[i])<<")"<<"->";
	}
	cout<<"("<<get<0>(p[w-1])<<","<<get<1>(p[w-1])<<")"<<endl;
} 

inline int read()
{
	int a=0,f=1;
	char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		a=(a<<3)+(a<<1)+(c^'0');
		c=getchar();
	}
	return a*f;
}

inline void dfs(int x,int y)
{
	if(x==fx && y==fy)
	{
		flag=true;
		print(tem);
		return;
	}
	for(int i=0;i<4;i++)
	{
		int a=x+dx[i],b=y+dy[i];
		if(a<1 || a>m || b<1 || b>n) continue;//出界
		if(!g[a][b]) continue;//访问过
		g[a][b]=0;
		tem++;
		p.push_back({a,b});
		dfs(a,b);
		g[a][b]=1;//回溯
		p.pop_back();
		tem--;
	}
}

int main()
{
	m=read(),n=read(); 
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			g[i][j]=read();
		}
	}
	sx=read(),sy=read(),fx=read(),fy=read();
	g[sx][sy]=0;
	p.push_back({sx,sy});
	dfs(sx,sy);
	if(flag==false) printf("%d",-1);
}
2024/7/25 11:27
加载中...