[解答-伯俊]19238タクシー台

63781 ワード

白駿テキストリンク

に答える
BFS
時間の複雑さ
O(n^2)
第一の考え

所定の地図情報に顧客番号

を追加する.

あなたの場所と到着地の情報をそれぞれリストに

にリストします.

顧客番号リスト

を作成する.
=>複数の顧客が同じ宛先を共有している場合、情報が上書きされるためエラーが発生します.
改善案

指定の地図情報は

に触らない

ダブルディック便情報

実施方法

乗せられるお客様を探しています[BFS]-2020 2
すべてのお客様の位置を見つけたら、min(key)を使って優先度の高いお客様を選択します.

客を乗せて目的地へ[BFS]-20*20

が失敗した場合、-1は

を返します.

戻り値の確認

が目的地に到着すると燃料

が更新される.

20*20、すべてのお客様が乗車していることを確認します

はまた、搭載可能なお客様がc訪問中にTrueで表示され、

例外処理

お客様ですが、目的地に到着できない場合、

、お客様の送迎がなければ

到着地に新規のお客様がいる場合

同じ場所に複数のお客様が到着した場合

チップ

で与えられた地図情報

に触れないでください.

deepcopy

をしないでください

をデバッグするときは、ツールを使用せずに印刷してみてください.その後、確認のために追加のテスト・インスタンスを迅速に作成する必要があります.

役立つテストケース
https://www.acmicpc.net/board/view/58112

# 6 5 19
# 1 0 0 0 1 0
# 1 0 1 0 1 0
# 1 0 1 0 1 0
# 1 0 1 0 1 0
# 1 0 1 0 1 0
# 0 0 1 0 0 0
# 1 3
# 6 1 1 6
# 1 6 6 2
# 5 2 2 4
# 6 5 6 6
# 4 6 1 2

# ans = 59

20 400 500000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
17 14
1 1 5 5
1 2 5 5
1 3 5 5
1 4 5 5
1 5 5 5
1 6 5 5
1 7 5 5
1 8 5 5
1 9 5 5
1 10 5 5
1 11 5 5
1 12 5 5
1 13 5 5
1 14 5 5
1 15 5 5
1 16 5 5
1 17 5 5
1 18 5 5
1 19 5 5
1 20 5 5
2 1 5 5
2 2 5 5
2 3 5 5
2 4 5 5
2 5 5 5
2 6 5 5
2 7 5 5
2 8 5 5
2 9 5 5
2 10 5 5
2 11 5 5
2 12 5 5
2 13 5 5
2 14 5 5
2 15 5 5
2 16 5 5
2 17 5 5
2 18 5 5
2 19 5 5
2 20 5 5
3 1 5 5
3 2 5 5
3 3 5 5
3 4 5 5
3 5 5 5
3 6 5 5
3 7 5 5
3 8 5 5
3 9 5 5
3 10 5 5
3 11 5 5
3 12 5 5
3 13 5 5
3 14 5 5
3 15 5 5
3 16 5 5
3 17 5 5
3 18 5 5
3 19 5 5
3 20 5 5
4 1 5 5
4 2 5 5
4 3 5 5
4 4 5 5
4 5 5 5
4 6 5 5
4 7 5 5
4 8 5 5
4 9 5 5
4 10 5 5
4 11 5 5
4 12 5 5
4 13 5 5
4 14 5 5
4 15 5 5
4 16 5 5
4 17 5 5
4 18 5 5
4 19 5 5
4 20 5 5
5 1 5 5
5 2 5 5
5 3 5 5
5 4 5 5
5 5 5 6
5 6 5 5
5 7 5 5
5 8 5 5
5 9 5 5
5 10 5 5
5 11 5 5
5 12 5 5
5 13 5 5
5 14 5 5
5 15 5 5
5 16 5 5
5 17 5 5
5 18 5 5
5 19 5 5
5 20 5 5
6 1 5 5
6 2 5 5
6 3 5 5
6 4 5 5
6 5 5 5
6 6 5 5
6 7 5 5
6 8 5 5
6 9 5 5
6 10 5 5
6 11 5 5
6 12 5 5
6 13 5 5
6 14 5 5
6 15 5 5
6 16 5 5
6 17 5 5
6 18 5 5
6 19 5 5
6 20 5 5
7 1 5 5
7 2 5 5
7 3 5 5
7 4 5 5
7 5 5 5
7 6 5 5
7 7 5 5
7 8 5 5
7 9 5 5
7 10 5 5
7 11 5 5
7 12 5 5
7 13 5 5
7 14 5 5
7 15 5 5
7 16 5 5
7 17 5 5
7 18 5 5
7 19 5 5
7 20 5 5
8 1 5 5
8 2 5 5
8 3 5 5
8 4 5 5
8 5 5 5
8 6 5 5
8 7 5 5
8 8 5 5
8 9 5 5
8 10 5 5
8 11 5 5
8 12 5 5
8 13 5 5
8 14 5 5
8 15 5 5
8 16 5 5
8 17 5 5
8 18 5 5
8 19 5 5
8 20 5 5
9 1 5 5
9 2 5 5
9 3 5 5
9 4 5 5
9 5 5 5
9 6 5 5
9 7 5 5
9 8 5 5
9 9 5 5
9 10 5 5
9 11 5 5
9 12 5 5
9 13 5 5
9 14 5 5
9 15 5 5
9 16 5 5
9 17 5 5
9 18 5 5
9 19 5 5
9 20 5 5
10 1 5 5
10 2 5 5
10 3 5 5
10 4 5 5
10 5 5 5
10 6 5 5
10 7 5 5
10 8 5 5
10 9 5 5
10 10 5 5
10 11 5 5
10 12 5 5
10 13 5 5
10 14 5 5
10 15 5 5
10 16 5 5
10 17 5 5
10 18 5 5
10 19 5 5
10 20 5 5
11 1 5 5
11 2 5 5
11 3 5 5
11 4 5 5
11 5 5 5
11 6 5 5
11 7 5 5
11 8 5 5
11 9 5 5
11 10 5 5
11 11 5 5
11 12 5 5
11 13 5 5
11 14 5 5
11 15 5 5
11 16 5 5
11 17 5 5
11 18 5 5
11 19 5 5
11 20 5 5
12 1 5 5
12 2 5 5
12 3 5 5
12 4 5 5
12 5 5 5
12 6 5 5
12 7 5 5
12 8 5 5
12 9 5 5
12 10 5 5
12 11 5 5
12 12 5 5
12 13 5 5
12 14 5 5
12 15 5 5
12 16 5 5
12 17 5 5
12 18 5 5
12 19 5 5
12 20 5 5
13 1 5 5
13 2 5 5
13 3 5 5
13 4 5 5
13 5 5 5
13 6 5 5
13 7 5 5
13 8 5 5
13 9 5 5
13 10 5 5
13 11 5 5
13 12 5 5
13 13 5 5
13 14 5 5
13 15 5 5
13 16 5 5
13 17 5 5
13 18 5 5
13 19 5 5
13 20 5 5
14 1 5 5
14 2 5 5
14 3 5 5
14 4 5 5
14 5 5 5
14 6 5 5
14 7 5 5
14 8 5 5
14 9 5 5
14 10 5 5
14 11 5 5
14 12 5 5
14 13 5 5
14 14 5 5
14 15 5 5
14 16 5 5
14 17 5 5
14 18 5 5
14 19 5 5
14 20 5 5
15 1 5 5
15 2 5 5
15 3 5 5
15 4 5 5
15 5 5 5
15 6 5 5
15 7 5 5
15 8 5 5
15 9 5 5
15 10 5 5
15 11 5 5
15 12 5 5
15 13 5 5
15 14 5 5
15 15 5 5
15 16 5 5
15 17 5 5
15 18 5 5
15 19 5 5
15 20 5 5
16 1 5 5
16 2 5 5
16 3 5 5
16 4 5 5
16 5 5 5
16 6 5 5
16 7 5 5
16 8 5 5
16 9 5 5
16 10 5 5
16 11 5 5
16 12 5 5
16 13 5 5
16 14 5 5
16 15 5 5
16 16 5 5
16 17 5 5
16 18 5 5
16 19 5 5
16 20 5 5
17 1 5 5
17 2 5 5
17 3 5 5
17 4 5 5
17 5 5 5
17 6 5 5
17 7 5 5
17 8 5 5
17 9 5 5
17 10 5 5
17 11 5 5
17 12 5 5
17 13 5 5
17 14 5 5
17 15 5 5
17 16 5 5
17 17 5 5
17 18 5 5
17 19 5 5
17 20 5 5
18 1 5 5
18 2 5 5
18 3 5 5
18 4 5 5
18 5 5 5
18 6 5 5
18 7 5 5
18 8 5 5
18 9 5 5
18 10 5 5
18 11 5 5
18 12 5 5
18 13 5 5
18 14 5 5
18 15 5 5
18 16 5 5
18 17 5 5
18 18 5 5
18 19 5 5
18 20 5 5
19 1 5 5
19 2 5 5
19 3 5 5
19 4 5 5
19 5 5 5
19 6 5 5
19 7 5 5
19 8 5 5
19 9 5 5
19 10 5 5
19 11 5 5
19 12 5 5
19 13 5 5
19 14 5 5
19 15 5 5
19 16 5 5
19 17 5 5
19 18 5 5
19 19 5 5
19 20 5 5
20 1 5 5
20 2 5 5
20 3 5 5
20 4 5 5
20 5 5 5
20 6 5 5
20 7 5 5
20 8 5 5
20 9 5 5
20 10 5 5
20 11 5 5
20 12 5 5
20 13 5 5
20 14 5 5
20 15 5 5
20 16 5 5
20 17 5 5
20 18 5 5
20 19 5 5
20 20 5 5

ans = 500023

コード#コード#
既存

from collections import deque

def start_bfs(y,x,d):
    deq = deque()
    if start[y][x] > 1 and not customer[start[y][x]]:
        Cs.append([y,x,d,start[y][x]])
        return
    deq.append([y,x,d])
    visited[y][x] = True

    while deq:
        y,x,d = deq.popleft()
        for dir in range(4):
            ny, nx = y + direct[dir][0], x + direct[dir][1]
            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and start[ny][nx] > 1 and not customer[start[ny][nx]]:
                Cs.append([ny , nx, d + 1, start[ny][nx]])
                deq.append([ny, nx, d + 1])
                visited[ny][nx] = True
            elif 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and start[ny][nx] != 1:
                deq.append([ny, nx, d + 1])
                visited[ny][nx] = True


def dest_bfs(lst):
    y,x,fuel,idx = lst
    if end[y][x] == idx and fuel <= tank:
        dest.append(y)
        dest.append(x)
        return 0
    deq=deque()
    deq.append([y,x,0])
    visited[y][x] = True

    while deq:
        y,x,d = deq.popleft()
        for dir in range(4):
            ny, nx = y + direct[dir][0], x + direct[dir][1]
            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and end[ny][nx] == idx and fuel+d+1 <= tank:
                dest.append(ny)
                dest.append(nx)
                return d+1
            elif 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and end[ny][nx] != 1 and fuel+d+1 <= tank:
                deq.append([ny, nx, d + 1])
                visited[ny][nx] = True
    return -1

direct = [(-1,0),(0,1),(1,0),(0,-1)]
N,M,tank = map(int,input().split())
start = [list(map(int,input().split())) for _ in range(N)]
end = [[0]*N for _ in range(N)]
sy,sx = map(int,input().split())
sy,sx = sy-1,sx-1
adj = {i:[] for i in range(2,M+2)}
customer = [False]*(M+2)
for i in range(2,M+2):
    t = list(map(int,input().split()))
    ts,te = t[:2],t[2:]
    ts[0], ts[1] = ts[0] - 1, ts[1] - 1
    te[0], te[1] = te[0] - 1, te[1] - 1
    adj[i].append(ts)
    adj[i].append(te)
    start[ts[0]][ts[1]] = i
    end[te[0]][te[1]] = i
for i in range(N):
    for j in range(N):
        if start[i][j] == 1:
            end[i][j] = 1
isEnd = False
while not isEnd:
    isEnd = True
    Cs = []
    visited = [[False] * N for _ in range(N)]
    start_bfs(sy,sx,0)

    # 가까운 후보 추려내기
    if not Cs:
        fl = -1
        break
    c = min(Cs, key=lambda x: (x[2],x[0],x[1]))

    # 목적지 찾기
    dest = []
    visited = [[False]*N for _ in range(N)]
    fl = dest_bfs(c)
    if fl == -1:
        isEnd = True
        break
    else:
        sy,sx = dest
        tank = tank - c[2] - fl + fl * 2
        customer[c[3]] = True

    for num in range(2,M+2):
        if not customer[num]:
            isEnd = False

if fl == -1:
    print(-1)
else:
    print(tank)

改善する

from _collections import deque

def find_customer(y,x,d):
    if customers.get((y,x)) is not None and c_visited[y][x]:
        Cs.append([y,x,d])
        return
    deq = deque()
    deq.append([y,x,d])
    visited[y][x] = True

    while deq:
        y,x,d = deq.popleft()
        for dir in range(4):
            ny, nx = y + direct[dir][0], x + direct[dir][1]
            if 0 <= ny < N and 0 <= nx < N and not matrix[ny][nx] and not visited[ny][nx] and c_visited[ny][nx]:
                Cs.append([ny,nx,d+1])
                deq.append([ny,nx,d+1])
                visited[ny][nx] = True
            elif 0 <= ny < N and 0 <= nx < N and not matrix[ny][nx] and not visited[ny][nx]:
                deq.append([ny, nx, d + 1])
                visited[ny][nx] = True


def move(lst):
    y,x,fuel = lst
    ey,ex = customers[(y,x)]
    if (y,x) == (ey,ex):
        dest.append(y)
        dest.append(x)
        return 0
    deq = deque()
    deq.append([y,x,0])
    visited[y][x] = True

    while deq:
        y,x,d = deq.popleft()
        for dir in range(4):
            ny, nx = y + direct[dir][0], x + direct[dir][1]
            if 0 <= ny < N and 0 <= nx < N and not matrix[ny][nx] and not visited[ny][nx] and (ny,nx) == (ey,ex) and fuel+d+1 <= tank:
                dest.append(ny)
                dest.append(nx)
                return d+1
            elif 0 <= ny < N and 0 <= nx < N and not matrix[ny][nx] and not visited[ny][nx] and fuel+d+1 <= tank:
                deq.append([ny,nx,d+1])
                visited[ny][nx] = True

    return -1

def check():
    cnt = 0
    for i in range(N):
        for j in range(N):
            if c_visited[i][j]:
                cnt += 1
    if cnt > 0: # 아직 남아있는 손님이 있다면
        return False
    else:
        return True


answer = -1
direct = [(-1,0),(0,1),(1,0),(0,-1)]
N,M,tank = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(N)]
sy,sx = map(int,input().split())
sy,sx = sy-1,sx-1
c_visited = [[False]*N for _ in range(N)] # 손님이 있으면 True
customers = {}
for i in range(M):
    t = list(map(int,input().split()))
    for j in range(4):
        t[j] -= 1
    ts, te = t[:2], t[2:]
    customers[(ts[0],ts[1])] = (te[0],te[1])
    c_visited[ts[0]][ts[1]] = True

isEnd = False
while not isEnd:
    isEnd = True
    Cs = []
    visited = [[False]*N for _ in range(N)]

    find_customer(sy,sx,0)
    # 손님 후보 뽑기
    if not Cs:
        answer = -1
        break
    c = min(Cs, key=lambda x:(x[2],x[0],x[1]))
    # 손님 태우고 출발
    dest = []
    visited = [[False] * N for _ in range(N)]
    fl = move(c)
    if fl == -1:
        answer = -1
        break
    else:
        tank = tank - c[2] + fl
        sy,sx = dest
        c_visited[c[0]][c[1]] = False

    if not check():
        isEnd = False
    else:
        answer = tank

print(answer)

Reference

この問題について([解答-伯俊]19238タクシー台), 我々は、より多くの情報をここで見つけました https://velog.io/@psj8532/문제풀이-백준-19238.-스타트-택시

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

android 8.0 textViewフォント特性の自動縮小

VCプロジェクトワンタッチコンパイルスクリプト