[hackerrank][python]Queen’s Attack II

題目連結: https://www.hackerrank.com/challenges/queens-attack-2/problem

一開始想說用遞迴去解，但是有些測資會直接讓記憶體爆炸(100000的棋盤)，最後只好改成用 while 迴圈去解決，算是一個不錯的練習~

遞迴:

def gogo(arr, r, c, d):
    if r + d[0] < 0 or c + d[1] < 0 or r + d[0] >= len(arr) or c + d[1] >= len(arr):
        return 0
    else:
        if arr[c + d[1]][r + d[0]] == 0:
            return 1 + gogo(arr, r + d[0], c + d[1], d)
        else:
            return 0
direct = [[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1]]
# Complete the queensAttack function below.
def queensAttack1(n, k, r_q, c_q, obstacles):
    ans = 0
    arr = [[0 for i in range(n)] for j in range(n)]
for l in obstacles:
        arr[l[1] - 1][l[0] - 1] = 1
for d in direct:
        ans += gogo(arr, r_q - 1, c_q - 1, d)
return ans

while 迴圈:

def queensAttack(n, k, r_q, c_q, obstacles):
    direct = [[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1]]
    ans = 0
    o_set = set([(x, y) for y, x in obstacles])
    for d in direct:
        r = r_q
        c = c_q
        while True:
            r += d[1]
            c += d[0]
            
            if r == 0 or c == 0 or r == n + 1 or c == n + 1:
                break
            if (c, r) in o_set:
                break
            
            ans += 1
    return ans