2.1 最基础的"穷竭搜索" 广度优先搜索
在H * W的地图上有N个奶酪工厂,分别生产硬度为1-N的奶酪。有一只吃货老鼠准备从老鼠洞出发吃遍每一个工厂的奶酪。老鼠有一个体力值,初始时为1,每吃一个工厂的奶酪体力值增加1(每个工厂只能吃一次),且老鼠只能吃硬度不大于当前体力值的奶酪。
老鼠从当前格走到相邻的无障碍物的格(上下左右)需要时间1单位,有障碍物的格不能走。走到工厂上时即可吃到该工厂的奶酪,吃奶酪时间不计。问吃遍所有奶酪最少用时。
输入:第一行三个整数H(1 <= H <= 1000)、W(1 <= W <=1000)、N(1 <= N <= 9),之后H行W列为地图, "."为空地, "X"为障碍物,"S"为老鼠洞, 1-N代表硬度为1-N的奶酪的工厂。(中文翻译参考了http://bbs.byr.cn/#!article/ACM_ICPC/73337?au=Milrivel)
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.......
思路:吃货必须按照工厂N值从小到大的顺序吃,否则体力不济。所以这个题目其实就是求按顺序遍历地图上12345……这几个点的最短路径。说到最短路径,当然就是bfs了。
分析:简单迷宫问题。不同的是,老鼠需要按1-N 的顺序把奶酪吃完。用广度优先搜索很容易求出起点到终点的最小步数。初始时,求起点到硬度值为 1 的奶酪的最小步数;接着将起点重置为此位置,继续求此位置到达硬度值为 2 的奶酪;如此类推。因此这里只需做N 次广度优先搜索,并累计其值即可。
int
w, h, n;
char
map[1024][1024];
// 各点到当前工厂的距离
int
d[1024][1024];
const
int
direction[4][2] = {
{ -1, 0 },
{ 1, 0 },
{ 0, -1 },
{ 0, 1 },
};
int
factory[16][2];
typedef
pair<
int
,
int
> P;
// Parameter: const int & sx 起点x
// Parameter: const int & sy 起点y
// Parameter: const int & gx 终点x
// Parameter: const int & gy 终点y
int
bfs(
const
int
& sx,
const
int
& sy,
const
int
& gx,
const
int
& gy)
{
//memset(d, -1, sizeof(d));
for
(
int
i = 0; i < h; ++i)
{
for
(
int
j = 0; j < w; ++j)
{
d[j][i] = -1;
}
}
queue<P> que;
que.push(P(sx, sy));
d[sx][sy] = 0;
while
(que.size())
{
const
P p = que.front(); que.pop();
// 如果是终点就结束
if
(p.first == gx && p.second == gy)
{
break
;
}
// 四方向漫游
for
(
int
i = 0; i < 4; ++i)
{
int
nx = p.first + direction[i][0];
int
ny = p.second + direction[i][1];
// 是否可以移动,并且该点没有访问过
if
(0 <= nx && nx < w && 0 <= ny && ny < h && map[nx][ny] !=
'X'
&& d[nx][ny] == -1)
{
que.push(P(nx, ny));
d[nx][ny] = d[p.first][p.second] + 1;
}
}
}
return
d[gx][gy];
}
int
main(
int
argc,
char
*argv[])
{
cin >> h >> w >> n;
for
(
int
i = 0; i < h; ++i)
{
for
(
int
j = 0; j < w; ++j)
{
cin >> map[j][i];
}
}
for
(
int
i = 0; i < h; ++i)
{
for
(
int
j = 0; j < w; ++j)
{
if
(map[j][i] ==
'S'
)
{
factory[0][0] = j;
factory[0][1] = i;
map[j][i] =
'.'
;
}
else
if
(
isdigit
(map[j][i]))
{
int
index = map[j][i] -
'0'
;
factory[index][0] = j;
factory[index][1] = i;
}
}
}
int
step = 0;
for
(
int
i = 0; i < n; ++i)
{
// 按顺序吃遍中华
step += bfs(factory[i][0], factory[i][1], factory[i + 1][0], factory[i + 1][1]);
}
cout << step << endl;
return
0;
}
int H, W, N; 16 char maze[MAX_H][MAX_W + 1]; 17 18 int sx, sy; //start 19 int d[MAX_H][MAX_W]; //steps 20 21 const int dx[4] = {-1, 1, 0, 0}; 22 const int dy[4] = {0, 0, -1, 1}; 23 24 int bfs(char c){ 25 //init 26 for(int i = 0; i < H; i ++){ 27 fill(d[i], d[i] + W, INF); 28 } 29 d[sx][sy] = 0; 30 queue<P> que; 31 que.push(P(sx, sy)); 32 33 while(!que.empty()){ 34 P p = que.front(); 35 que.pop(); 36 //arrive 37 if(maze[p.first][p.second] == c){ 38 //reset 39 sx = p.first; 40 sy = p.second; 41 break; 42 } 43 44 for(int i = 0; i < 4; i ++){ 45 int nx = p.first + dx[i], ny = p.second + dy[i]; 46 47 if(0 <= nx && nx < H && 0 <= ny && ny < W && maze[nx][ny] != 'X' && d[nx][ny] == INF){ 48 que.push(P(nx, ny)); 49 d[nx][ny] = d[p.first][p.second] + 1; 50 } 51 } 52 } 53 return d[sx][sy]; 54 } 55 56 void solve(){ 57 //start 58 for(int i = 0; i < H; i ++){ 59 for(int j = 0; j < W; j ++){ 60 if(maze[i][j] == 'S'){ 61 sx = i; 62 sy = j; 63 break; 64 } 65 } 66 } 67 //bfs for 1-N 68 int ans = 0; 69 for(int i = 1; i <= N; i ++){ 70 ans += bfs('0' + i); 71 } 72 printf("%d\n", ans); 73 } 74 75 int main(int argc, char const *argv[]){ 76 77 scanf("%d %d %d", &H, &W, &N); 78 for(int i = 0; i < H; i ++){ 79 scanf("%s", maze[i]); 80 } 81 solve(); 82 83 return 0; 84 }Read full article from AOJ 0558 Cheese 《挑战程序设计竞赛(第2版)》练习题答案 � 码农场