題意
https://vjudge.net/problem/CodeForces-1236D
最近，愛麗絲得到了一個新玩偶，它甚至可以走路！
愛麗絲為玩偶建造了一個迷宮，并想對其進行測驗，迷宮具有n行和m列，有k個障礙物，第i個障礙物位于單元格（xi,yi?）上，這意味著第xi?個行與第yi?列相交的單元格上存在一個禁止通過的障礙物，
然而，玩偶有著缺陷，在同一單元格（包括起始單元格）中，它最多只能筆直走或右轉一次，它無法進入有障礙物的單元格或走出迷宮的界限之外，
現在，愛麗絲正在控制娃娃的動作，她將玩偶放入單元格（1,1）（即迷宮的左上角）中，最初，玩偶的朝向從(1,1)向著(1,m)，她想讓玩偶恰好穿過一次所有單元格而沒有障礙，玩偶的行動可以在任何地方結束，愛麗絲的想法可以實作嗎？
思路
這題細節非常多，但是也很好寫，直接模擬就行了，但是一步一步的走肯定會T，我們可以維護每一行、每一列的障礙物，上下左右邊界，每次走的時候直接跳到最近的障礙物前面即可，
注意幾個坑：
1.（1，1）正前方（1，2）有障礙物，可以直接右轉，這里要特判一下，
2.每跳一次，判斷前面那個位置是否是不可行的點，這里我用上述的上下左右邊界判斷，如果是，那么走不通了，break即可，
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
vector<ll> g[N],gg[N];
int main()
{
std::ios::sync_with_stdio(false);
ll n,m,k;
cin>>n>>m>>k;
int bb=0;
for(int i=1; i<=k; i++)
{
ll x,y;
cin>>x>>y;
g[x].push_back(y);
gg[y].push_back(x);
}
ll l=1,r=m,u=1,d=n;
ll x=1,y=1,sum=1;
if(k==0)
{
cout<<"Yes"<<endl;
return 0;
}
int sz=g[x].size(),flag=0;
if(sz==m-1)
flag=1;
ll t;//最近的符合要求的位置+1
while(1)
{
if(!flag)
{
sz=g[x].size();
t=r+1;
for(int i=0; i<sz; i++)
{
if(g[x][i]>y)
t=min(t,g[x][i]);
}
if(t-y==1)
break;
sum+=t-y-1,y=t-1,r=t-1-1,u=x+1;
}
// cout<<x<<" "<<y<<" "<<sum<<endl;
// cout<<l<<" "<<r<<" "<<u<<" "<<d<<endl;
sz=gg[y].size();
t=d+1;
for(int i=0; i<sz; i++)
{
if(gg[y][i]>x)
{
t=min(t,gg[y][i]);
}
}
if(t-x==1)
break;
sum+=t-x-1,x=t-1,d=t-1-1;
// cout<<x<<" "<<y<<" "<<sum<<endl;
// cout<<l<<" "<<r<<" "<<u<<" "<<d<<endl;
sz=g[x].size();
t=l-1;
for(int i=0; i<sz; i++)
{
if(g[x][i]<y)
{
t=max(t,g[x][i]);
}
}
if(y-t==1)
break;
sum+=y-t-1,y=t+1,l=t+1+1;
// cout<<x<<" "<<y<<" "<<sum<<endl;
// cout<<l<<" "<<r<<" "<<u<<" "<<d<<endl;
sz=gg[y].size();
t=u-1;
for(int i=0; i<sz; i++)
{
if(gg[y][i]<x)
{
t=max(t,gg[y][i]);
}
}
if(x-t==1)
break;
sum+=x-t-1,x=t+1,u=t+1+1;
// cout<<x<<" "<<y<<" "<<sum<<endl;
// cout<<l<<" "<<r<<" "<<u<<" "<<d<<endl;
}
// cout<<sum<<endl;
if(sum+k==n*m)
{
cout<<"Yes"<<endl;
}
else
cout<<"No"<<endl;
return 0;
}
/*
2 2 2
1 2
2 2
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/121133.html
標籤：其他
下一篇：《演算法》筆記 10 - 無向圖