# 【題解】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())
g = []
for i in range(N):
#開始倒的地方只有 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()
```