【題解】ZeroJudge d406: 倒水時間

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d406
【解題想法】BFS

  • S = 1  代表水可以往上流
  • S = 2  代表水不能往上流
  • 移動方向只有 [0 ~ 5 – S)
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=105;
int g[maxn][maxn], steps[maxn][maxn];
int dr[] = {1, 0, 0, -1};
int dc[] = {0, -1, 1, 0};

int main() {
    int S, N, M, Case=1;
    int r, c, nr, nc;
    
    while (cin >> S) {
        memset(g, 0, sizeof(g));
        memset(steps, 0, sizeof(steps));
        cin >> N >> M;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                cin >> g[i][j];
            }
        }
        for (int j=0; j<M; j++) {
            if (g[0][j] == 1) {
                r = 0;
                c = j;
                break;
            }
        }
        
        queue<pair<int,int> > q;
        q.push({r, c});
        steps[r][ c] = 1;
        while (!q.empty()) {
            r = q.front().first;
            c = q.front().second;
            q.pop();
            for (int i=0; i<5-S; i++) {
                nr = r + dr[i];
                nc = c + dc[i];
                if (nr<0 || nr>=N || nc<0 || nc >= M) continue;
                if (g[nr][nc] == 0) continue;
                if (steps[nr][nc] > 0) continue;
                steps[nr][nc] = steps[r][ c]+1;
                q.push({nr, nc});
            }
        }
        cout << "Case "<< Case++ << ":\n";
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                cout << steps[i][j] << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

Python code (credit: Amy Chou)

import sys
dr = [1, 0, 0, -1] #row direction
dc = [0, -1, 1, 0] #col direction
Case = 1

for line in sys.stdin:
    S = int(line.strip())
    N, M = map(int, sys.stdin.readline().strip().split())
    g = []
    for i in range(N):
        g.append(list(map(int, sys.stdin.readline().strip().split())))
    #開始倒的地方只有 1 個且只在第一列倒
    for j in range(M):
        if g[0][j] == 1:
            r = 0
            c = j
            break
    steps = [[0 for j in range(M)] for i in range(N)]
    q = [(r, c)]
    steps[r][ c] = 1
    while q:
        r, c = q.pop(0)
        for i in range(5 - S):
            nr = r + dr[i]
            nc = c + dc[i]
            if nr < 0 or nr >= N or nc < 0 or nc >= M:
                continue
            if g[nr][nc] == 0:
                continue
            if steps[nr][nc] > 0:
                continue
            steps[nr][nc] = steps[r][ c] + 1
            q.append((nr, nc))
    print(f"Case {Case}:")
    Case += 1
    for i in range(N):
        for j in range(M):
            print(steps[i][j], " ", sep='', end='')
        print()
分享本文 Share with friends