BFS+思维-poj-3182-The Grove

2013年10月08日21:06　阅读: 15630 次

题目大意：

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

分享到：更多

今日更新

头条新闻本类焦点本类推荐