30 分 dfs 求调
查看原帖
30 分 dfs 求调
807584
mengqifeng楼主2025/1/14 19:00
#include <iostream>
using namespace std;
int r,c;
bool flag;
bool vis[115][80];
char pic[115][80];
int record_x[115];
int record_y[85];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
bool judge(int x,int y)
{
	if(x<=0||y<=0||x>r||y>c)return false;
	if(vis[x][y]==true)return false;
	if(pic[x][y]=='*')return false;
	return true;
}
void dfs(int x,int y,int sum)
{
	record_x[sum]=x;
	record_y[sum]=y;
	if(x==r&&y==c)
	{
		flag=1;
		for(int i=1;i<sum;i++)
			cout<<record_x[i]<<" "<<record_y[i]<<"\n";
		cout<<r<<" "<<c;
		return;
	}
	if(flag==1)return;

	for(int i=0;i<4;i++)
	{
		int xx=dx[i]+x,yy=dy[i]+y;
		if(judge(xx,yy))
		{
			vis[xx][yy]=1;
			dfs(xx,yy,sum+1);
		}
	}
	return ;
}
int main()
{
	cin>>r>>c;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
			cin>>pic[i][j];
	dfs(1,1,1);
	
	return 0;
}
2025/1/14 19:00
加载中...