BFS+思维-poj-3182-The Grove

 

有一片紧凑的森林不能访问，给一个起点，问从起点出发，可以上下左右斜对角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 55  
  
char 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;  
}  

 

补充：软件开发 , C++ ,