高中生程式解題系統 e287: 機器人的路徑(BFS)－資工趴趴熊的小天地

Content

你有一台機器人，它會在地上爬。
經過了8756天的觀察過後，你發現了它移動的規律。
它會從地圖中數值最低的那格出發，然後不斷走向周圍的格子中數值最低且沒被走過的格子。
直到它沒有路可以走。
(周圍的定義是上下左右，共4格)

Input

單筆輸入

第一行有
兩個數字 n, m 代表地圖的大小
接著有 n 行，每行有 m 個數字，用空白隔開
每個數字都非負且小於 1000000 且都不相等

Output

輸出路徑上的數字總和

Sample Input #1

1 7
1 2 3 4 5 6 7

Sample Output #1

python:

方法一二其實一樣，不同寫法而已

方法一:

dx=[-1,1,0,0]
dy=[0,0,-1,1]
while True:
    try:
        n, m = map(int, input().split())
        a = [[0 for j in range(m)] for i in range(n)]
        x0=-1
        y0=-1
        min=10000000
        """找出最小值"""
        for i in range(n):
            N = list(map(int, input().split()))
            for j, k in enumerate(N):#j會跑0123 k會跑輸入的元素
                """這邊同時輸入數字，同時找最小值"""
                a[i][j] = k
                if k<min:x0 = i;y0 = j;min = k
        ans=0
        arr= [[0 for j in range(m)] for i in range(n)]
        while min<10000000:
            arr[x0][y0]=1#代表有經過的
            ans+=min
            next_x=-1
            next_y=-1
            next_min=10000000
            for i in range(4):#開始上下左右找最小的
                nx=x0+dx[i]
                ny=y0+dy[i]
                if (nx >= 0) and (nx < n) and (ny >= 0) and (ny < m):#界定範圍
                    if arr[nx][ny] == 0 and (a[nx][ny] < next_min):#沒走過且上下左右最小
                        next_x=nx
                        next_y=ny
                        next_min=a[nx][ny]
            x0=next_x
            y0=next_y
            min=next_min
        print(ans)
    except:
        break

方法二:

direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def walk(i, j):
    global ans
    vis[i][j] = True#走到的位置改為true
    ans += M[i][j]
    min = 1000000
    min_i, min_j = 0, 0
    for k in direction:
        if 1 <= i + k[0] <= n and 1 <= j + k[1] <= m and not vis[i + k[0]][j + k[1]]:
        #if 今天在範圍裡面 and 沒有走過
            if M[i + k[0]][j + k[1]] < min:
                min = M[i + k[0]][j + k[1]]
                min_i, min_j = i + k[0], j + k[1]
    if min == 1000000: return
    else: walk(min_i, min_j)
while True:
    try:
        n, m = map(int, (input().split()))
    except EOFError:
        break
    M = [[0 for j in range(m + 1)] for i in range(n + 1)]
    vis = [[False for j in range(m + 1)] for i in range(n + 1)]
    Min = 1000000
    st_i, st_j = 0, 0
    ans = 0
    for i in range(1, n + 1):
        M[i][1:] = list(map(int, input().split()))
        for j in range(1, m + 1):
            temp = M[i][j]
            if temp < Min:
                Min = temp
                st_i, st_j = i, j
    #print(M)會產生一個上面排 左邊排為0的二維list
    walk(st_i, st_j)
    print(ans)