「Bzoj 1656」「Usaco2006 Jan」 The Grove 树木 (BFS)

发表于 | 分类于 | | + s

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

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

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

#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;
}
------ 本文结束 ------