AOJ0558 Cheese

AOJ0558 Cheese

問題

今年も JOI 町のチーズ工場がチーズの生産を始め,ねずみが巣から顔を出した.JOI 町は東西南北に区画整理されていて,各区画は巣,チーズ工場,障害物,空き地のいずれかである.ねずみは巣から出発して全てのチーズ工場を訪れチーズを 1 個ずつ食べる.

この町には,N 個のチーズ工場があり,どの工場も1種類のチーズだけを生産している.チーズの硬さは工場によって異なっており,硬さ 1 から N までのチーズを生産するチーズ工場がちょうど 1 つずつある.

ねずみの最初の体力は 1 であり,チーズを 1 個食べるごとに体力が 1 増える.ただし,ねずみは自分の体力よりも硬いチーズを食べることはできない.

ねずみは,東西南北に隣り合う区画に 1 分で移動することができるが,障害物の区画には入ることができない.チーズ工場をチーズを食べずに通り過ぎることもできる.すべてのチーズを食べ終えるまでにかかる最短時間を求めるプログラムを書け.ただし,ねずみがチーズを食べるのにかかる時間は無視できる.

入力

入力は H+1 行ある.1 行目には 3 つの整数 H,W,N (1 ≤ H ≤ 1000,1 ≤ W ≤ 1000,1 ≤ N ≤ 9) がこの順に空白で区切られて書かれている.2 行目から H+1 行目までの各行には,'S','1', '2', ..., '9','X','.' からなる W 文字の文字列が書かれており,各々が各区画の状態を表している.北から i 番目,西から j 番目の区画を (i,j) と記述することにすると (1 ≤ i ≤ H, 1 ≤ j ≤ W),第 i+1 行目の j 番目の文字は,区画 (i,j) が巣である場合は 'S' となり,障害物である場合は 'X' となり,空き地である場合は '.' となり,硬さ 1, 2, ..., 9 のチーズを生産する工場である場合はそれぞれ '1', '2', ..., '9' となる.入力には巣と硬さ 1, 2, ..., N のチーズを生産する工場がそれぞれ 1 つずつある.他のマスは障害物または空き地であることが保証されている.ねずみは全てのチーズを食べられることが保証されている.

出力

すべてのチーズを食べ終えるまでにかかる最短時間(分)を表す整数を 1 行で出力せよ.

入出力例

入力例 1

1
2
3
4
3 3 1
S..
...
..1

出力例 1

1
4

入力例 2

1
2
3
4
5
4 5 2
.X..1
....X
.XX.S
.2.X.

出力例 2

1
12

入力例 3

1
2
3
4
5
6
7
8
9
10
11
10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......

出力例 3

1
91

答え

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

struct Point {
int x, y, d; // d 为距离起点的路径长度
Point() {}
Point(int x, int y, int d) : x(x), y(y), d(d) {}
};

char maze[1001][1001];
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };
int sx[10], sy[10];
int h, w, n, ans = 0;

int bfs(int sx, int sy, int gx, int gy);

int main() {
scanf("%d %d %d", &h, &w, &n);
for (int i = 0; i < h; ++i) {
scanf("%s", &maze[i]);
}
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (maze[i][j] == 'S') {
sx[0] = i;
sy[0] = j;
}
if (maze[i][j] >= '1' && maze[i][j] <= '9') {
int t = maze[i][j] - '0';
sx[t] = i;
sy[t] = j;
}
}
}

for (int i = 1; i <= n; ++i) {
ans += bfs(sx[i-1], sy[i-1], sx[i], sy[i]);
}
printf("%d\n", ans);
return 0;
}

int bfs(int sx, int sy, int gx, int gy) {
bool vis[1001][1001];
fill(vis[0], vis[0]+1001*1001, false);
queue <Point> que;
que.push(Point(sx, sy, 0));
vis[sx][sy] = true;

while (!que.empty()) {
Point p = que.front();
que.pop();
for (int i = 0; i < 4; ++i) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
int nd = p.d + 1;
if (nx < 0 || nx >= h || ny < 0 || ny >= w || maze[nx][ny] == 'X' || vis[nx][ny])
continue;
if (nx == gx && ny == gy)
return nd;
que.push(Point(nx, ny, nd));
vis[nx][ny] = true;
}
}
}

分析

  1. 求 S,1,2,...,N 的顺序最短路径之和。
  2. 宽度优先搜索,挨个找最短路径。
# AOJ

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×