Codeforces Round #504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)-E. Down or Right-白红宇

Codeforces Round #504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)-E. Down or Right

阅读量：4114 次

发布时间：2019-05-25

本文共 853 字，大约阅读时间需要 2 分钟。

E. Down or Right

题意：给你一个n*n的方格，找出一条可能从（1,1）走到（n，n）的路径，每次只能向下走或者向右走，如果两个位置之间的曼哈顿距离大于等于（n-1），你可以询问两个点是否可达，如果可达得到“yes”，不可达得到“no”。询问的次数不能超过4*n。

思路：我们从（1,1）向右向下询问，从（n，n）向上向左询问。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            using namespace std;bool check(int x1,int y1,int x2,int y2){ printf("? %d %d %d %d\n",x1,y1,x2,y2); fflush(stdout); char str[10]; scanf("%s",str); if(str[0]=='Y') return true; return false;}queue
            
              q;stack
             
               s;int main(){ int n; scanf("%d",&n); int x1=1,y1=1; while(n-x1+n-y1>n-1) { if(check(x1,y1+1,n,n)) { q.push('R'); y1++; } else { q.push('D'); x1++; } } int x2=n,y2=n; while(x2!=x1||y2!=y1) { if(check(1,1,x2-1,y2)) { x2--; s.push('D'); } else { s.push('R'); y2--; } } printf("! "); while(!q.empty()) { char c=q.front(); q.pop(); cout<