BZOJ 1656: [Usaco2006 Jan] The Grove 树木(神奇的bfs之射线法)

Posted by 111qqz on Friday, April 15, 2016


1656: [Usaco2006 Jan] The Grove 树木

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 143  Solved: 88 [Submit][Status][Discuss]


The pasture contains a small, contiguous grove of trees that has no ‘holes’ in the middle of the it. Bessie wonders: how far is it to walk around that grove and get back to my starting position? She's just sure there is a way to do it by going from her start location to successive locations by walking horizontally, vertically, or diagonally and counting each move as a single step. Just looking at it, she doesn't think you could pass ‘through’ the grove on a tricky diagonal. Your job is to calculate the minimum number of steps she must take. Happily, Bessie lives on a simple world where the pasture is represented by a grid with R rows and C columns (1 <= R <= 50, 1 <= C <= 50). Here's a typical example where ‘.’ is pasture (which Bessie may traverse), ‘X’ is the grove of trees, ‘’ represents Bessie's start and end position, and ‘+’ marks one shortest path she can walk to circumnavigate the grove (i.e., the answer): …+… ..+X+.. .+XXX+. ..+XXX+ ..+X..+ …+++ The path shown is not the only possible shortest path; Bessie might have taken a diagonal step from her start position and achieved a similar length solution. Bessie is happy that she's starting ‘outside’ the grove instead of in a sort of ‘harbor’ that could complicate finding the best path.


    贝茜很想知道,最少需要多少步能围绕树林走一圈,最后回到起点.她能上下左右走,也能走对角线格子.牧场被分成R行C列(1≤R≤50,1≤C≤50).下面是一张样例的地图,其中“.”表示贝茜可以走的空地,  “X”表示树林,  “*”表示起点.而贝茜走的最近的路已经特别地用“+”表示出来.




  • Line 1: Two space-separated integers: R and C

  • Lines 2..R+1: Line i+1 describes row i with C characters (with no spaces between them).



  • Line 1: The single line contains a single integer which is the smallest number of steps required to circumnavigate the grove.


Sample Input

6 7 ……. …X… ..XXX.. …XXX. …X… ……*

Sample Output





/* ***********************************************
Author :111qqz
Created Time :2016年04月14日 星期四 22时29分15秒
File Name :code/bzoj/1656.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int dx8[8]={1,1,1,0,0,-1,-1,-1};
const int dy8[8]={1,0,-1,1,-1,1,0,-1};
const int inf = 0x3f3f3f3f;
const int N=55;
char maze[N][N];
int n,m;
int ans;
int f[2][N][N];//f[k][i][j]表示的是从起点走到(i,j),射线法与多边形交点的奇偶性的k的最短路。
bool die[N][N]; //画一条射线。。
struct node
    int x,y;
    int f;//f表示改点射线法与多边形交点的奇偶性。
    bool ok()
    if (x>=0&&x<n&&y>=0&&y<m&&maze[x][y]!='X') return true;
    return false;

void bfs()
    s.f = 0;

    while (!q.empty())
    node pre = q.front() ; q.pop();
    for ( int i = 0 ; i < 8 ; i++)
        node nxt;
        nxt.x = pre.x + dx8[i];
        nxt.y = pre.y + dy8[i];
        if (!nxt.ok()) continue;
        if ((die[pre.x][pre.y]||die[nxt.x][nxt.y])&&nxt.y<=pre.y) continue;
        if (die[nxt.x][nxt.y]&&!f[1][nxt.x][nxt.y])
        f[1][nxt.x][nxt.y] = f[pre.f][pre.x][pre.y]+1;
        nxt.f = 1;
        }else if (!f[pre.f][nxt.x][nxt.y])
        f[pre.f][nxt.x][nxt.y] = f[pre.f][pre.x][pre.y] + 1;
        nxt.f = pre.f;

int main()
    #ifndef  ONLINE_JUDGE 

    scanf("%d %d",&n,&m);
    for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
    for ( int i = 0 ; i < n ; i++)
        for ( int j = 0 ; j < m ; j++)
        if (maze[i][j]=='*')
            s.x = i ;
            s.y = j;
        if (maze[i][j]=='X')
            tree.x = i ;
            tree.y = j;

    for ( int i = 0 ; i < n ; i++) if (i+tree.x<n) die[i+tree.x][tree.y] = true;

  #ifndef ONLINE_JUDGE  
    return 0;