欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

VK Cup 2017 - Qualification 1 C. Cycle In Maze(bfs+最短路+贪心+思维)

程序员文章站 2022-07-12 12:30:53
...

题目链接
VK Cup 2017 - Qualification 1 C. Cycle In Maze(bfs+最短路+贪心+思维)
VK Cup 2017 - Qualification 1 C. Cycle In Maze(bfs+最短路+贪心+思维)
题意:给定n*m的网格图,给你起点x,问存不存路径满足从X出发最后回到X刚好K步,如果存在输出字典序最小的路径。
思路:字典序最小只要规定一下方向很容易贪心构造,麻烦的是怎么让他又回到起点呢?这里学到了大佬们的方法,可以一开始先求起点到其他点的最短路,假设当前还剩x步才满K,点(i,j)到起点的距离小于等于X的话就可以走,否则不行,就是卡距离,逼他回到起点。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
const int maxn=1e3+5;
const int inf=1e9+1;
int n,m,k,cnt,st,ed,d[maxn][maxn];
char s[maxn][maxn];
bool check(int x,int y)
{
	return (x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]!='*'); 
} 
void bfs()
{
	queue<pair<int,int>>q;
	q.push({st,ed});
	d[st][ed]=0;
	while(!q.empty())
	{
		pair<int,int>t=q.front();
		q.pop();
		int x=t.first,y=t.second,nx,ny;
		for(int i=0;i<4;++i)
		{
			nx=x+dir[i][0],ny=y+dir[i][1];
			if(check(nx,ny)&&d[nx][ny]>d[x][y]+1) q.push({nx,ny}),d[nx][ny]=d[x][y]+1;
		}
	}
}
int main()
{
	string ans,str="DLRU";
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;++i)
	{
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;++j)
		{
			if(s[i][j]=='X') st=i,ed=j;
			d[i][j]=inf;
		}
	 } 
	 bfs();
	 int x=st,y=ed,nx,ny;
	 for(int i=1;i<=k;++i)
	 {
	 	int flag=0;
	 	for(int j=0;j<4;++j)
	 	{
	 		nx=x+dir[j][0],ny=y+dir[j][1];
	 		if(check(nx,ny)&&d[nx][ny]<=k-i) {flag=1;ans+=str[j];break;}
		 }
		 if(!flag) {
		 	printf("IMPOSSIBLE\n");return 0;
		 }
		 x=nx,y=ny;
	 }
	 cout<<ans<<endl;
}