VK Cup 2017 - Qualification 1 C. Cycle In Maze(bfs+最短路+贪心+思维)
程序员文章站
2022-07-12 12:30:53
...
题目链接
题意:给定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;
}