[白俊]2564保安Python


警備員


質問する


東根は無人会社の警備員で、呼び出しを受けるたびにパトカーを運転して駆けつけた.東根が担当している場所は長方形の街で、街の真ん中を通り抜けて、車を通す道はありません.この街の境界には無人の店がある.
例えば、横長が10、縦長が5の街区境界では、3つの店が無人で当直を依頼している.<図1>に示すように、それらは1,2,3で表され、同根はXで表される位置にある.
<図1>
1号店がコールを受けたとき、東根は時計回りにブロックを移動し、移動距離は12だった.逆に反時計回りに移動すると移動距離は18となる.そのため、東根から1号店までの最短距離は12です.同様に、東根の位置から2番ショップまでの最短距離は6、3番ショップまでの最短距離は5です.
ブロックの大きさ、店舗の個数、位置、および同ルートの位置が与えられた場合、プログラミングプログラムは、同ルートの位置と各店舗との間の最短距離の和を求める.

入力


第1の行は、ブロックの横方向の長さと縦方向の長さを順次与える.2行目は店の数を与える.街区の横長と縦の長さ、商店の個数はすべて100以下の自然数です.次の行に1つの店の位置があります.店の位置は2つの自然数で表示されます.1番目の数字は店の方向を示しています.1つは街の北、2つは街の南、3つは街の西、4つは街の東に店があります.2番目の数字は、商店がブロックの北側または南側に位置するときのブロックの左境界からの距離を表し、商店がブロックの東または西に位置する場合、ブロックの上境界からの距離を表す.最後の行は、同じルートの位置と店の位置が同じ方法を示しています.商店の位置や東根の位置は街区の制高点にはならない.

しゅつりょく


1行目は、同じルートの位置と各店舗間の最短距離の和を印刷します.

解決策

  • まず座標を与えず、東西南北に基づいて各点と東根の座標を入力します.
  • を考慮して時計回りの場合と、時計回りを考慮しない場合とを分け、上根をその方向を基準に巡回させて最適値を求める.
  • x,y = map(int,input().split())
    num = int(input())
    stores = [list(map(int,input().split())) for i in range(num+1)] #상근이까지 
    
    
    for store in stores : 
        if store[0] == 1 :
            store[0] = store[1]
            store[1] = y
    
        elif store[0] == 2:
            store[0] = store[1]
            store[1] = 0
    
        elif store[0] == 3 :
            store[0] = 0
            store[1] = y-store[1]
    
        else :
            store[0] = x
            store[1] = y-store[1]
        
    s = stores[-1]
    stores = stores[:-1]
    
    cnt = 0
    for store in stores :
    
        if s[0] == 0 :
            direction = 1
        else :
            direction = 0
    
        sangx,sangy = s[0],s[1]
        sol1=sol2=0
    
        #시계 
        dy = [0,1,0,-1]
        dx = [-1,0,1,0] 
    
        if s[0] == 0 :
            direction = 1
        elif s[0] == x:
            direction = 3
        elif s[1] == 0 :
            direction = 0
        else :
            direction = 2
    
        while [sangx,sangy] != store :
            sangx += dx[direction]
            sangy += dy[direction] 
            if sangx<0 or sangy<0 or sangx>x or sangy>y :
                sangx -= dx[direction]
                sangy -= dy[direction] 
                direction = (direction+1)%4
                sangx += dx[direction]
                sangy += dy[direction] 
            sol1 +=1 
    
        #반시계
        dy = [0,1,0,-1]
        dx = [1,0,-1,0] 
    
        if s[0] == 0 :
            direction = 3
        elif s[0] == x:
            direction = 1
        elif s[1] == 0 :
            direction = 0
        else :
            direction = 2
        sangx,sangy = s[0],s[1]
    
        while [sangx,sangy] != store :
            sangx += dx[direction]
            sangy += dy[direction] 
            if sangx<0 or sangy<0 or sangx>x or sangy>y :
                sangx -= dx[direction]
                sangy -= dy[direction] 
                direction = (direction+1)%4
                sangx += dx[direction]
                sangy += dy[direction] 
            sol2 +=1 
        cnt += min(sol1,sol2)
    print(cnt)