题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int D[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int T[2][4]={{3,2,1,0},{1,0,3,2}};
int n;
int mx,my;
vector<int> ax,ay;
int tag[205][205];
bool st[205][205][4];
bool rt[205];
struct Node
{
int x=0,y=0,id=-1;
void f()
{
x=lower_bound(ax.begin(), ax.end(), x)-ax.begin()+1;
y=lower_bound(ay.begin(), ay.end(), y)-ay.begin()+1;
}
void input(int i)
{
cin>>y>>x;
id=i;
}
}pt[205];
void f(vector<int> &v)
{
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
}
bool sol()
{
memset(st,0,sizeof st);
bool flag=0;
int d=1;
int x=pt[n+1].x,y=pt[n+1].y;
while(1){
if(x==pt[0].x&&y==pt[0].y){
flag=1;
break;
}
if(x<1||x>mx||y<1||y>my||st[x][y][d])break;
st[x][y][d]=1;
if(tag[x][y]!=-1)d=T[tag[x][y]][d];
x+=D[d][0],y+=D[d][1];
}
return flag;
}
int main()
{
cin>>n;
pt[0].input(0);
for(int i=1;i<=n;i++){
pt[i].input(i);
char c;
cin>>c;
rt[i]=(c=='/');
}
for(int i=0;i<=n+1;i++){
ax.push_back(pt[i].x);
ay.push_back(pt[i].y);
}
f(ax),f(ay);
mx=ax.size(),my=ay.size();
memset(tag,-1,sizeof tag);
for(int i=0;i<=n+1;i++){
pt[i].f();
if(i>=1&&i<=n)tag[pt[i].x][pt[i].y]=rt[pt[i].id];
}
if(sol()){
cout<<0;
return 0;
}
for(int i=1;i<=n;i++){
tag[pt[i].x][pt[i].y]^=1;
if(sol()){
cout<<i;
return 0;
}
tag[pt[i].x][pt[i].y]^=1;
}
cout<<-1;
}