2023.1.11 PM 10:00 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=i401 出題者 : 2022年6月APCS 標籤 : 二分搜尋法 難易度 : 3
解題想法 : 定義四種狀態(往左、往右、往上、往下)，並分別實作。 由於遞迴會有過深的問題，丟上去Zerojudge會NA(95%)，因此需使用for迴圈或switch...case...break實作，此處筆者在寫Python時使用前者，C++時則使用後者。 實作上可以利用下列資料結構輔助 : 。same_x[i] 儲存當x值同為i時的所有y值(需排序) 。same_y[i] 儲存當y值同為i時的所有x值(需排序) 。T[(x,y)]儲存在(x,y)處的鏡子方向。 。X -> set 將x值去重，於same_x[i]排序時使用 。Y -> set 將y值去重，於same_y[i]排序時使用 由於四種狀態大同小異，此處列出通用的二分搜尋使用時機。 x(y)相同時 : 找比自己更上面(右邊)的位置(y(x)更大)，(C++,Python)使用(upper_bound(),bisect.bisect_right())，若搜尋不到該值，就表示出界了。 找比自己更下面(左邊)的位置(y(x)更小)，(C++,Python)使用(lower_bound(),bisect.bisect_left())先搜出「大於等於」當前y(x)的值，然後他前面一格的值就會是小於當前的y(x)的值，但若搜出來的結果就是開頭，可以直接判為失敗。 此題實作較為複雜，建議可以自己重新釐清觀念並寫出自己的版本。
//C++ language
#include<iostream>
#include<map> //map
#include<utility> //pair
#include<vector> //vector
#include<unordered_set> //unordered_set
#include<algorithm> //sort()
#define it vector<int>::iterator
using namespace std;
int main(){
int n,times=0; cin>>n;
map<pair<int,int>,bool>T;
map<int,vector<int>>same_x,same_y;
unordered_set<int>X,Y;
for(int i=0;i<n;i++){
int x,y,t;
cin>>x>>y>>t;
T[{x,y}]=t;
same_x[x].push_back(y);
same_y[y].push_back(x);
X.insert(x);
Y.insert(y);
}
for(int i:X)sort(same_x[i].begin(),same_x[i].end());
for(int i:Y)sort(same_y[i].begin(),same_y[i].end());
int now=3,x=0,y=0;
//now: 1->左, 2->上, 3->右, 4->下, 0->沒路
while(now){
switch(now){
case 1:{
it next_left_x=lower_bound(same_y[y].begin(),same_y[y].end(),x);
if(next_left_x==same_y[y].begin()){
now=0;
continue;
}
next_left_x=prev(next_left_x);
times++;
x=*next_left_x;
if(T[{x,y}]) // t="\"
now=2;
else // t="/"
now=4;
}break;
case 2:{
it next_up_y=upper_bound(same_x[x].begin(),same_x[x].end(),y);
if(next_up_y==same_x[x].end()){
now=0;
continue;
}
times++;
y=*next_up_y;
if(T[{x,y}]) // t="\"
now=1;
else // t="/"
now=3;
}break;
case 3:{
it next_right_x=upper_bound(same_y[y].begin(),same_y[y].end(),x);
if(next_right_x==same_y[y].end()){
now=0;
continue;
}
times++;
x=*next_right_x;
if(T[{x,y}]) // "\"
now=4;
else // "/"
now=2;
}break;
case 4:{
it next_down_y=lower_bound(same_x[x].begin(),same_x[x].end(),y);
if(next_down_y==same_x[x].begin()){
now=0;
continue;
}
next_down_y=prev(next_down_y);
times++;
y=*next_down_y;
if(T[{x,y}]) // t="\"
now=3;
else // t="/"
now=1;
}break;
}
}
cout<<times<<"\n";
return 0;
}
## Python language
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound
n=int(input())
same_x=dict(); same_y=dict(); T=dict()
X=set(); Y=set()
same_y[0]=[]
for i in range(n):
x,y,t=map(int,input().split())
T[(x,y)]=t
X.add(x); Y.add(y)
if same_x.get(x)==None:
same_x[x]=[y]
else: same_x[x].append(y)
if same_y.get(y)==None:
same_y[y]=[x]
else: same_y[y].append(x)
for i in X: same_x[i].sort()
for i in Y: same_y[i].sort()
## now: 左:1, 上:2, 右:3, 下:4, 沒路:0
now=3
x=y=times=0
while now:
if now==1:
next_left_x=lower_bound(same_y[y],x)
if next_left_x==0: break
next_left_x-=1
times+=1
x=same_y[y][next_left_x]
if T[(x,y)]: # \
#toup
now=2
else: # /
#todown
now=4
elif now==2:
next_up_y=upper_bound(same_x[x],y)
if next_up_y==len(same_x[x]): break
times+=1
y=same_x[x][next_up_y]
if T[(x,y)]: # \
#toleft
now=1
else: # /
#toright
now=3
elif now==3:
next_right_x=upper_bound(same_y[y],x)
if next_right_x==len(same_y[y]): break
times+=1
x=same_y[y][next_right_x]
if T[(x,y)]: # \
#todown
now=4
else: # /
#toup
now=2
elif now==4:
next_down_y=lower_bound(same_x[x],y)
if next_down_y==0:
now=0
continue
next_down_y-=1
times+=1
y=same_x[x][next_down_y]
if T[(x,y)]: # \
#toright
now=3
else: # /
#toleft
now=1
print(times)
