i401. 3. 雷射測試

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)

相關文章