GCJ round 1B A (python)

Code Jam - Google’s Coding Competitions

Aしか解けず５点差で通過できず。C何とかして部分点取りたかった。インタラクティブはまだ入力の仕方がわからないので諦め。
Aは４方向に i 回目に 2**(i-1) 移動でき、(x,y) = (0,0) から、最終的に目的の座標に到達する最小手順を答える問題。
ゴールから逆算して (0,0) に到達する方法を考えた
i 回目以降ではどのように移動しても、移動距離が 2**(i-1) の倍数にしかならないことを考えれば、
i 回目 で (x,y) = (a,b) にいるとすると、
(a,b) == (0,0) or (a >> i & 1 ) ^ ( b >> i & 1 ) == 1 がIMPOSSIBLE とならないための必要条件となるとわかる。この前に abc の XOR sum 4 を解いていたのが大当たりした。だからこそ通過しておきたかったが…
D - Xor Sum 4

あとは (a,b) が (0,0) に到着する、もしくはIMPOSSIBLE になるまで４方向に bfs をしていけばよい
ｘ方向かｙ方向かは c >> i & 1 == 1 となる方になる
bfs の実装が慣れてないので、座標と回数と文字列を全て持たせたままループさせた。
ゴールから逆算しているので、移動方向と反対方向の文字を持たせていることに注意。

n = int(input())
from collections import deque

def bfs(a,b,cnt,d):
    que = deque([])
    que.append((a, b, cnt, d))
    ans = 'IMPOSSIBLE'
    while que:
        p = que.popleft()
        if p[0] == 0 and p[1] == 0:
            ans = p[3]
            break
        if p[0]>>p[2]&1 == 1 and p[1]>>p[2]&1 != 1:
              que.append(((p[0]-2**p[2],p[1],p[2]+1,p[3]+'E'))) #E
              que.append(((p[0]+2**p[2],p[1],p[2]+1,p[3]+'W'))) #W
        if p[0]>>p[2]&1 != 1 and p[1]>>p[2]&1 == 1:
              que.append(((p[0],p[1]-2**p[2],p[2]+1,p[3]+'N'))) #N
              que.append(((p[0],p[1]+2**p[2],p[2]+1,p[3]+'S'))) #S
    return ans
  
    
for j in range(n):
    a, b = [int(i) for i in input().split()]
    ns = bfs(a,b,0,'')
    print('Case #{}: {}'.format(j+1,ns))