我们来自五湖四海,不为别的,只因有共同的爱好,为中国互联网发展出一分力!

BFS+思维-poj-3182-The Grove

2013年10月08日21:06 阅读: 12693 次
题目大意:
 
有一片紧凑的森林不能访问,给一个起点,问从起点出发,可以上下左右斜对角8个方向走,求最小的步数能够围住森林并且回到起点。
 
解题思路:
 
思维+BFS.
 
先找到森林到右边界的一条线段。显然,要求的路径肯定要穿过这条线段。所以从这条线段中的每个点两遍BFS,一遍控制开始的方向非下,另一遍控制开始的方向非上。到达终点截止。求出最小的路径长度。
 
另外一种思路。从起点开始BFS,求出起点到该线段各点的距离两个距离,然后更新。
 
代码:
 
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#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; 
分享到: 更多
蓝客门户
©2001-2017 中国蓝客联盟 版权所有.
关于蓝客联盟历史宗旨章程技术服务联系我们蓝客社区