浙江福彩3d走势图
我們來自五湖四海,不為別的,只因有共同的愛好,為中國互聯網發展出一分力!

BFS+思維-poj-3182-The Grove

2013年10月08日21:06 閱讀: 15487 次
題目大意:
 
有一片緊湊的森林不能訪問,給一個起點,問從起點出發,可以上下左右斜對角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-2019 中國藍客聯盟 版權所有.
關于藍客聯盟歷史宗旨章程技術服務聯系我們藍客社區

浙江福彩3d走势图