Aoj-0558 BFS搜索-白书习题

AOJ0558 Cheese BFS搜索
九月摸鱼之后的第一篇正式题解…
题目链接:https://vjudge.net/problem/Aizu-0558

晚上回宿舍写的,因为久了没敲题,几乎是照着书敲得,正好这题就是板子题,稍微改了下就过了

チーズ ()
問題
今年も 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
3 3 1
S..

..1
出力例 1
4
入力例 2
4 5 2
.X..1
….X
.XX.S
.2.X.
出力例 2
12
入力例 3
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
91
問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。
纯BFS搜索,就是更新下搜索的起点终点就行,因为有的路走过了还得走一次;每一次都是全新的BFS
AC CODE :

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
69
70
71
72
73

#include <iostream>
#include <queue>
#define inf 0x3f3f3f
using namespace std;
const int maxn=1001;
typedef pair<int,int>P;
char map[maxn][maxn];
int d[maxn][maxn];
int sx,sy;
int gx,gy;
int dx[4]{1,0,-1,0},dy[4]={0,1,0,-1};
int ans=0;
int h,l,w;
int bfs(){
queue<P>wyh;
for(int i=0;i<h;i++){
for(int j=0;j<l;j++){
d[i][j]=inf;
}
}
wyh.push(P(sx,sy));
d[sx][sy]=0;
while(wyh.size()){
P _=wyh.front();
wyh.pop();
if(_.first==gx&&_.second==gy)break;
for(int i=0;i<4;i++){
int nx=_.first+dx[i];
int ny=_.second+dy[i];
if(0<=nx&&nx<h&&0<=ny&&ny<l&&map[nx][ny]!='X'&&d[nx][ny]==inf){
wyh.push(P(nx,ny));
d[nx][ny]=d[_.first][_.second]+1;
}
}
}
return d[gx][gy];
}
int main(){
ios::sync_with_stdio(false);
cin>>h>>l>>w;
for(int i=0;i<h;i++){
for(int j=0;j<l;j++){
cin>>map[i][j];
}
}
for(int i=0;i<h;i++){
for(int j=0;j<l;j++){
if(map[i][j]=='S'){
sx=i;
sy=j;
}
}
}
int cnm=w;
while(w){
for(int i=0;i<h;i++){
for(int j=0;j<l;j++){
if(map[i][j]=='1'+cnm-w){
gx=i;
gy=j;
ans+=bfs();
sx=i;
sy=j;
w--;
break;
}
}
}
}
cout<<ans<<endl;
return 0;
}

coswindy

-------------本文结束感谢您的阅读-------------