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

北京pk10冠亚和遗漏:BFS+思维-poj-3182-The Grove

2013年10月08日21:06 阅读: 12821 次
题目大意:
 
有一片紧凑的森林不能访问,给一个起点,问从起点出发,可以上下左右斜对角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; 
分享到: 更多
蓝客门户
上海时时乐在线平台 北京pk10的开盘时间 上海时时乐最新开奖结果 北京快乐8赚钱方法 北京pk10挂机 北京pk10冠军8码计划
北京pk10冠亚和遗漏 北京pk10冠亚和遗漏 北京赛车pk10冠亚和 北京赛车冠军下期位置 上海时时乐杀号
北京pk10冠亚和对刷 北京pk10冠亚刷水 北京pk10冠亚和值计划 北京pk10冠亚刷水 北京pk10冠亚和值公式
北京pk10万能八码技巧 北京pk10官网 北京pk10计划官网 北京快乐8公式提前开奖 北京快乐8开奖结果查询 上海时时乐带线走势图
早点加盟店有哪些l 东北早餐加盟 自助早餐加盟 加盟早点店 中式早点加盟
江苏早点加盟 广式早餐加盟 卖早餐加盟 天津早点加盟 口口香早点加盟
早点加盟网 早餐早点店加盟 北京早点摊加盟 早餐馅饼加盟 烤肉加盟
加盟特色早点 春光早餐加盟 春光早餐加盟 早餐加盟哪个好 早点小吃加盟店
广东26选5好彩2奖金 广东十一选五 上海11选五开奖结果 内蒙古体彩十一选五 组码特码
福利彩票15选5 玩家世界娱乐 山西快乐十分开奖爱拼彩票网 上海快三走势图今天 双赢彩票手机版
幸运农场开奖结果 大乐透开奖直播 3d字谜 浙江11选5公式 湖北十一选五预测
北京快乐8开奖预测 快乐十分开奖记录 蓝博什么意思 2017香港特码生肖表 苹果重庆时时彩软件