本文主要是介绍Codeforces Round #593 (Div. 2) D. Alice and the Doll(模拟)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://codeforces.com/contest/1236/problem/D
题目大意：一个n*m的地图，上面有k个障碍物，从1 1出发，问能不能在只能右转且不能经过同一个点的情况下遍历所有不是障碍的点
题目思路：就是个模拟，用set维护每一行 每一列障碍的位置，每次二分得到下一次跳跃的位置，并且不断缩小行动范围，一直到无路可走。然后判断一下走的步数+k+1是不是等于n*m，加1是因为1 1没被算进去。需要注意的是一个特殊情况，就是初始的时候向右出不去，但是向下能出去，所以需要来一个flag记录是不是1 1撞了南墙
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const ll MAXN = 1e5+5;
const ll MOD = 1e9+7;
int n,m,k,x,y;
set<int>r[MAXN],c[MAXN];
int main()
{while(cin>>n>>m>>k){rep(i,1,n)r[i].clear();rep(i,1,m)c[i].clear();rep(i,1,k){cin>>x>>y;r[x].insert(y);c[y].insert(x);}rep(i,1,n){r[i].insert(0);r[i].insert(m+1);}rep(i,1,m){c[i].insert(0);c[i].insert(n+1);}int L=0,R=m+1,U=0,D=n+1;x=1,y=1;int dir=0,flag=0;ll ans=0;while(1){int xx=x,yy=y;if(dir==0){int temp=*r[x].lower_bound(y);y=min(R-1,temp-1);U=x;if(y==yy&&flag){break;}}if(dir==1){int temp=*c[y].lower_bound(x);x=min(D-1,temp-1);R=y;if(x==xx)break;}if(dir==2){int temp=*(--r[x].lower_bound(y));y=max(L+1,temp+1);D=x;if(y==yy)break;}if(dir==3){int temp=*(--c[y].lower_bound(x));x=max(U+1,temp+1);L=y;if(x==xx)break;}dir=(dir+1)%4;flag=1;ans+=abs(x-xx)+abs(y-yy);}if(ans+k+1==(ll)n*m)puts("Yes");else puts("No");}return 0;
}
这篇关于Codeforces Round #593 (Div. 2) D. Alice and the Doll(模拟)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
