BFS+思维-poj-3182-The Grove

题目链接：

http://poj.org/problem?id=3182

题目大意：

有一片紧凑的森林不能访问，给一个起点，问从起点出发，可以上下左右斜对角8个方向走，求最小的步数能够围住森林并且回到起点。

解题思路：

思维+BFS.

先找到森林到右边界的一条线段。显然，要求的路径肯定要穿过这条线段。所以从这条线段中的每个点两遍BFS，一遍控制开始的方向非下，另一遍控制开始的方向非上。到达终点截止。求出最小的路径长度。

另外一种思路。从起点开始BFS，求出起点到该线段各点的距离两个距离，然后更新。

代码：

#include<iostream>#include<cmath>#include<cstdio>#include<sstream>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<ctime>#include<bitset>#define eps 1e-6#define INF 0x3f3f3f3f#define PI acos(-1.0)#define ll __int64#define LL long long#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define Maxn 55char sa[Maxn][Maxn];int dir[8][2]={{-1,-1},{-1,0},{-1,1},{1,1},{1,0},{1,-1},{0,1},{0,-1},}; //前三个表示向上，中间三个表示向下，后面连个表示左右int n,m,lex,ley,sx,sy,aa;struct Pos{    int x,y,step;}q[Maxn*Maxn],ss;bool vis[Maxn][Maxn];bool istrue(int x,int y) //找出该线段的左起点{    if(y==1||sa[x][y-1]!='X')        return false;    for(int i=y;i<=m;i++)        if(sa[x][i]=='X')            return false;    return true;}bool iscan(int x,int y){    if(x<1||x>n||y<1||y>m)        return false;    return true;}bool isline(Pos a) //是否在该线段上{    if(a.x==lex&&a.y>=ley)        return true;    return false;}void bfs(int flag){    bool first=true;    memset(vis,false,sizeof(vis));    int head=0,tail=-1;    q[++tail]=ss;    vis[ss.x][ss.y]=true;    while(head<=tail)    {        Pos cur=q[head];        head++;        for(int i=0;i<8;i++)        {            if(isline(cur)&&i<6) //控制改线段上点的方向 非下或非上            {                if(flag) //0向上                {                    if(i<=2)                        continue;                }                else //1向下                {                    if(i>=3)                        continue;                }            }            int x=cur.x+dir[i][0],y=cur.y+dir[i][1];            if(!iscan(x,y)||sa[x][y]=='X'||vis[x][y])                continue;            if(x==sx&&y==sy)            {                aa+=cur.step+1;                return ;            }            vis[x][y]=true;            Pos tmp={x,y,cur.step+1};            q[++tail]=tmp;        }    }}int main(){    while(~scanf("%d%d",&n,&m))    {        for(int i=1;i<=n;i++)        {            scanf("%s",sa[i]+1);            for(int j=1;j<=m;j++)                if(sa[i][j]=='*')                    sx=i,sy=j;  //找到起始点        }        for(int i=1;i<=n;i++)            for(int j=1;j<=m;j++)            {                if(istrue(i,j)) //找任意一条连接森林和右边界的线段的左端点                {                    lex=i,ley=j;                    j=m+1,i=n+1;                }            }        int ans=INF;        for(int i=ley;i<=m;i++)        {            aa=0;            ss.x=lex,ss.y=i,ss.step=0;            bfs(0); //非向下            bfs(1); //非向上            ans=min(ans,aa);        }        printf("%d\n",ans);    }   return 0;}