1023E

题意:

  交互题。在一个有障碍地图中,问如何走才能从(1,1)走到(n,n),只能向右或者向左走。每次询问两个点,回复你这两个点能不能走通。

思路:

  只用最多2*n-2次询问。从(1,1),能向右走就向右走,不能就向下走,直到走到斜对角线上。从(n,n)出发,能向上走就向上走,不能就向左走,直到走到斜对角线上。

  因为保证有路,所以最后输出(1,1)出发的正向路径,加上从(n,n)出发的反向路径。

#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
//#pragma GCC optimize(3)
//#pragma comment(linker, "/STACK:102400000,102400000") //c++
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull; typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行
#define REP(i , j , k) for(int i = j ; i < k ; ++i)
//priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFF; //
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //
const int mod = 1e9+; const double PI=acos(-1.0); template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
}
// #define _DEBUG; //*//
#ifdef _DEBUG
freopen("input", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
/*-----------------------showtime----------------------*/
const int maxn = ;
int vis[maxn];
int n; int get(int x,int y,int flag){
char g[];
if(flag)
cout<<"? "<<x<<" "<<y<<" "<<n<<" "<<n<<endl;
else cout<<"? "<<<<" "<<<<" "<<x<<" "<<y<<endl;
cin>>g;
if(g[] == 'Y')return ;
else if(g[] == 'N') return ;
return ;
} vector<int>up,down;
void solve(){
int x = , y = ;
while(x+y<=n+){
if(get(x,y,)){
y++;up.pb();
}
else {
x++;up.pb();
}
} x = n-,y = n; while(x+y>n){
if(get(x,y,)){
x--;down.pb();
}
else {
y--;down.pb();
}
}
} int main(){
cin>>n;
solve(); string ans = "";
for(int i=; i<up.size(); i++){
int tmp = up[i];
if(tmp==){
ans+="D";
}
else ans += "R";
} for(int i=down.size() - ; i>=; i--){
int tmp = down[i];
if(tmp==){
ans+="D";
}
else ans += "R";
}
cout<<"! "<<ans<<endl;
return ;
}

1023E

最新文章

  1. MyBatis 入门(一)
  2. MapReduce工作原理讲解
  3. ruby的加密方法整理(des rsa加密 加签)
  4. 【重走Android之路】【Java面向对象基础(一)】数据类型与运算符
  5. Hibernate一对一双向关联映射
  6. BZOJ2818: Gcd 莫比乌斯反演
  7. JAVA的可变类与不可变类
  8. [置顶] RFS的web自动化验收测试——常见问题指引
  9. [置顶] think in java interview-高级开发人员面试宝典(七)
  10. 【strtok()】——分割字符串
  11. 最简化模型——css3分阶段动画效果(经过实测)
  12. iBrand 教程 0.1:Windows + Homestead 5 搭建 Laravel 开发环境
  13. spring问题
  14. 2019The Preliminary Contest for ICPC China Nanchang National Invitational
  15. git操作远程仓库
  16. scrapy 爬虫框架(一)
  17. python selenium自动化点击页面链接测试
  18. Eclipse添加Spket插件实现ExtJs智能提示
  19. Jmeter之断言
  20. 优秀的PHP开发者是怎样炼成的?

热门文章

  1. 一个项目中:只能存在一个 WebMvcConfigurationSupport (静态文件失效之坑)
  2. MySql性能优化读书比较&lt;一&gt; 数据类型
  3. BGP属性控制实验
  4. 内容汇总(c语言)
  5. Java经典编程题
  6. LASSO原作者的论文,来读读看
  7. WPF界面的异步后台加载
  8. python3学习-logging模块
  9. 【Kubernetes 系列五】在 AWS 中使用 Kubernetes:EKS
  10. Windows下的bat原来可以为我们做很多