[Iroha 2019 Day3 D] おにごっこ 题解

· · 题解

考虑到如果你能看到彩叶并且彩叶快抓到你了，那么你一定就能往另一个方向跑，因为题目限制了迷宫的形态——没有死胡同。

所以如果她能抓到你，必然是迷宫存在一个“视线死角”——你要走到的目标格子旁边，她已经在等着“偷袭”你了——你一过去她就紧接着走过去，然后你就寄了。即考虑如下的例子（其中 ? 可以为 # / . 中的一种）：

????
?.#?
?..?
????

你在 (2,2)，她在 (3,3)，同时往 (3,2) 走，由于你一开始看不到她，所以你会被抓到。

避免上面的事情发生是很简单的，那就是你在非必要的情况下就不要动。显然在这种情况下，她不可能偷袭你，因为她到了一个地方并且与你的距离 =1，那么你必然可以看得到她，那个时候你再跑也来得及。

于是策略就十分明了了——只有在她与自己距离 =1 的时候选择另外一个方向跑路，其他情况下都不动。

放代码：

#include<bits/stdc++.h>
using namespace std;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
const string s="DURL";
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<string> a(n);
  for(auto &i:a)cin>>i;
  for(int r=0,x=1,y=1,px=-1,py=-1;r<1000;r++){
    if(abs(x-px)+abs(y-py)>1)cout<<'-'<<endl;
    else{
      for(int d=0;d<4;d++){
        int xx=x+dx[d],yy=y+dy[d];
        if((xx!=px||yy!=py)&&a[xx][yy]!='#'){
          x=xx,y=yy,cout<<s[d]<<endl; break;
        }
      } // 选择一个其他的方向跑路
    }
    cin>>px>>py,px--,py--;
  }
  return 0;
}