P4772只能用状压吗?本人用BFS跑全T了
  • 板块学术版
  • 楼主yegengghost
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/2/29 22:09
  • 上次更新2024/3/1 12:56:28
查看原帖
P4772只能用状压吗?本人用BFS跑全T了
791716
yegengghost楼主2024/2/29 22:09
#include<bits/stdc++.h>
#define int long long
using namespace std;
int r,c,n;
char ch[514][514];
int bx,by;
string ans;
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};
int sum;
bool vis[514][514];
int read()
{
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
void bfs(int x,int y,int num)
{
	if(x<1||x>r||y<1||y>c||ch[x][y]=='*'||vis[x][y])
		return ;
	if(ch[x][y]>='B'&&ch[x][y]<='Z')
	{
		sum+=num;
		ans+=ch[x][y];
		bx=x,by=y;
		return ;
	}
	for(int i=0;i<4;i++)
	{
		vis[x+dx[i]][y+dy[i]]=1;
		x+=dx[i];
		y+=dy[i];
		bfs(x,y,num+1);
	}
}
signed main()
{
	r=read();
	c=read();
	n=read();
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
		{
			cin>>ch[i][j];
			if(ch[i][j]=='A')
				bx=i,by=j;
		}
	ans="A";
	while(ans.length()<=n)
	{
		memset(vis,0,sizeof(vis));
		bfs(bx,by,0);
	}
	cout<<sum<<'\n';
	cout<<ans<<'\n';
	return 0;
}
2024/2/29 22:09
加载中...