Bzoj 1656(BFS)

bzoj 1656
luogu 2864
from: USACO 2006 Jan Sliver(USACO刷题第1题)

一道BFS。之前没看题解没什么思路搜索,看了题解后发现可以随便找一棵树然后垂直于坐标轴作一条射线,该线内的方块不可到达(相当于障碍物)。BFS记录到达每个点的最短步数,之后再在这条射线上进行合并局部解,得到最后的最优解。

本题咋一看就是一个BFS,但是他要求绕着树林走,那么画一条射线来分解问题,把原问题分解为各走一半的最优解,最后再进行合并,得到全走完的最优解

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
const int MAXN = 50 + 5;
const int dx[8] = {1,0,-1,0,1,-1,1,-1};
const int dy[8] = {0,1,0,-1,1,-1,-1,1};
struct node{int step, x, y;};
int r, c, s, t, woodx, woody, vi[MAXN][MAXN];
char m[MAXN][MAXN];
void bfs() {
queue<node> q;
vi[s][t] = 0; q.push((node){0,s,t});
while (!q.empty()) {
node p = q.front(); q.pop();
for (int i=0;i<8;i++) {
int tx = p.x + dx[i], ty = p.y + dy[i];
if (tx>0&&ty>0&&tx<=r&&ty<=c) {
if (m[tx][ty]=='.'&&vi[tx][ty]==-1) {
vi[tx][ty] = p.step + 1;
q.push((node){p.step + 1,tx,ty});
}
}
}
}
}
void clear() {
for (int i=1;i<=r;i++)
for (int j=1;j<=c;j++) vi[i][j] = -1;
woodx = woody = 0;
}
void init() {
clear();
for (int i=1;i<=r;i++) {
for (int j=1;j<=c;j++) {
char ch;
while (ch!='.'&&ch!='X'&&ch!='*') ch = getchar();
m[i][j] = ch;
if (ch=='*') s = i, t = j;
if (!woodx&&ch=='X') woodx = i, woody = j;
ch = getchar();
}
}
for (int j=1;j<woody;j++) m[woodx][j] = '^';
}
void solve() {
bfs();
int ans = 1000000000;
for (int j=1;j<woody;j++) {
if (j-1>0&&vi[woodx-1][j-1]!=-1&&vi[woodx+1][j+1]!=-1) ans = min(ans, vi[woodx-1][j-1]+vi[woodx+1][j+1]);//1 6
if (vi[woodx-1][j]!=-1 &&vi[woodx+1][j]!=-1) ans = min(ans, vi[woodx-1][j]+ vi[woodx+1][j]);//2 5
if (j-1>0&&vi[woodx-1][j+1]!=-1&&vi[woodx+1][j-1]!=-1) ans = min(ans, vi[woodx-1][j+1]+vi[woodx+1][j-1]);//3 4
if (vi[woodx-1][j]!=-1 &&vi[woodx+1][j+1]!=-1) ans = min(ans, vi[woodx-1][j]+ vi[woodx+1][j+1]);//2 6
if (vi[woodx-1][j+1]!=-1&&vi[woodx+1][j]!=-1) ans = min(ans, vi[woodx-1][j+1]+vi[woodx+1][j]);//3 5
}
printf("%d\n", ans+2);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d", &r, &c)==2&&r&&c) init(), solve();
return 0;
}

------ 本文结束 ------