【分类讨论】【spfa】【BFS】Codeforces Round #416 (Div. 2) D. Vladik and Favorite Game
2024-08-25 23:06:58
那个人第一步肯定要么能向下走，要么能向右走。于是一定可以判断出上下是否对调，或者左右是否对调。
然后他往这个方向再走一走就能发现一定可以再往旁边走，此时就可以判断出另一个方向是否对调。
都判断出来以后，跑个spfa或者bfs就行了。
细节较多……有一些边界情况需要处理。比如终点在第一行或者第一列的情况。
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,int> Point;
Point ma[110*110*10];
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,m,End;
char a[110][110];
int num[110][110],pen;
queue<int>Q;
int dis[110*110*10],v[110*110*4*10],e,__next[110*110*4*10],first[110*110*10];
int pre[110*110*10];
bool inq[110*110*10];
void AddEdge(int U,int V){
v[++e]=V;
__next[e]=first[U];
first[U]=e;
}
void spfa(const int &s)
{
memset(dis,0x7f,sizeof(dis));
dis[s]=0; Q.push(s); inq[s]=1;
while(!Q.empty())
{
int U=Q.front();
for(int i=first[U];i;i=__next[i])
if(dis[v[i]]>dis[U]+1)
{
dis[v[i]]=dis[U]+1;
pre[v[i]]=U;
if(!inq[v[i]])
{
Q.push(v[i]);
inq[v[i]]=1;
}
}
Q.pop(); inq[U]=0;
}
}
Point path[110*110*10];
int p;
bool lr,ud;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%s",a[i]+1);
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
num[i][j]=++pen;
ma[pen]=make_pair(i,j);
if(a[i][j]=='F'){
End=num[i][j];
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)if(a[i][j]=='.' || a[i][j]=='F'){
for(int k=0;k<4;++k){
int tx=i+dx[k],ty=j+dy[k];
if(a[tx][ty]=='.' || a[tx][ty]=='F'){
AddEdge(num[i][j],num[tx][ty]);
}
}
}
} if(End==1){
return 0;
}
int x,y;
if((a[2][1]=='*' || n==1) && (a[1][2]=='.' || a[1][2]=='F')){
puts("R");
fflush(stdout);
scanf("%d%d",&x,&y);
if(x==1 && y==1){
lr=1;
}
while(a[x][y]!='F' && a[x+1][y]=='*'){
puts(lr ? "L" : "R");
fflush(stdout);
scanf("%d%d",&x,&y);
}
if(a[x][y]=='F'){
return 0;
}
puts("D");
fflush(stdout);
scanf("%d%d",&x,&y);
if(a[x][y]=='F'){
return 0;
}
if(x==1){
ud=1;
}
}
else if((a[1][2]=='*' || m==1) && (a[2][1]=='.' || a[2][1]=='F')){
puts("D");
fflush(stdout);
scanf("%d%d",&x,&y);
if(x==1 && y==1){
ud=1;
}
while(a[x][y]!='F' && a[x][y+1]=='*'){
puts(ud ? "U" : "D");
fflush(stdout);
scanf("%d%d",&x,&y);
}
if(a[x][y]=='F'){
return 0;
}
puts("R");
fflush(stdout);
scanf("%d%d",&x,&y);
if(a[x][y]=='F'){
return 0;
}
if(y==1){
lr=1;
}
}
else if((a[1][2]=='.' || a[1][2]=='F') && (a[2][1]=='.' || a[2][1]=='F')){
puts("R");
fflush(stdout);
scanf("%d%d",&x,&y);
if(x==1 && y==1){
lr=1;
puts("D");
fflush(stdout);
scanf("%d%d",&x,&y);
if(num[x][y]==End){
return 0;
}
if(x==1 && y==1){
ud=1;
}
}
else{
if(num[x][y]==End){
return 0;
}
puts("L");
fflush(stdout);
scanf("%d%d",&x,&y);
puts("D");
fflush(stdout);
scanf("%d%d",&x,&y);
if(num[x][y]==End){
return 0;
}
if(x==1 && y==1){
ud=1;
}
}
} spfa(num[x][y]);
int U=End;
while(U!=num[x][y]){
path[++p]=ma[U];
U=pre[U];
}
path[++p]=ma[num[x][y]];
for(int i=p;i>1;--i){
if(path[i-1].first-path[i].first==1){
puts(ud ? "U" : "D");
fflush(stdout);
scanf("%d%d",&x,&y);
}
if(path[i-1].first-path[i].first==-1){
puts(ud ? "D" : "U");
fflush(stdout);
scanf("%d%d",&x,&y);
}
if(path[i-1].second-path[i].second==1){
puts(lr ? "L" : "R");
fflush(stdout);
scanf("%d%d",&x,&y);
}
if(path[i-1].second-path[i].second==-1){
puts(lr ? "R" : "L");
fflush(stdout);
scanf("%d%d",&x,&y);
}
}
return 0;
}
最新文章
- I/O Techie 社区 --欢迎您的加入
- 每天一个linux命令（47）：iostat命令
- web基础
- Mac OSX系统下SVN客户端SCPlugin问题
- composer 报 zlib_decode(): data error
- windows串口通信的一个活动图
- Android-Socket传输 GPRS网络
- Ubuntu安装Adobe Reader
- Google Summer of Code 建议被接收的5个技巧
- java web基础 --- URL重定向Filter
- C# 调用C++dll出现的问题。
- 2018/1/28 每日一学 单源最短路的SPFA算法以及其他三大最短路算法比较总结
- lambda高级进阶--返回函数
- Android开发技巧——Camera拍照功能
- shell入门（二）:()、(())、[]、[[]]、{}
- js三种弹出框的用法
- iptables 认识 第二章
- Rails项目防止时序攻击
- Delphi接口的底层实现
- 如何使用mysql存储树形关系