首页 > 其他 > 详细

多点搜的bfs

时间:2019-03-23 22:24:53      阅读:179      评论:0      收藏:0      [点我收藏+]

Problem L. 跑图
Time limit: 1000ms
Memory limit: 65536KB
Description
跑图是 RPG 游戏中很烦躁的事情。玩家需要跑到距离他最近的传送点的位置。现在给你
一张???? × ????的方格图,每个方格中数值0表示为平地,数值1表示为传送点,你的任务是输出
一张???? × ????的矩阵,???????????????????????? ???????? 表示从(????,????)到距离它最近的传送点的距离。 这里的距离是曼
哈顿距离,(???? 1 ,???? 1 ) → (???? 2 ,???? 2 ) 的距离为|???? 1 − ???? 2 | + |???? 1 − ???? 2 |。
Input
第一行,有两个数????,????。接下来????行,每行????个数。
数据保证至少有一个传送点。
1 ≤ ???? ≤ 500,1 ≤ ???? ≤ 500
Output
????行,每行????个数,表示某个点到离它最近的传送点的位置。

把传送点都放到Q中,然后bfs就可(我是真的垃圾呀)

 1 #include <iostream>
 2 #include <cstring>
 3 #include <string>
 4 #include <map>
 5 #include <set>
 6 #include <algorithm>
 7 #include <fstream>
 8 #include <cstdio>
 9 #include <cmath>
10 #include <stack>
11 #include <queue>
12 using namespace std;
13 const double Pi=3.14159265358979323846;
14 typedef long long ll;
15 const int MAXN=5000+5;
16 const int dx[5]={0,0,0,1,-1};
17 const int dy[5]={1,-1,0,0,0};
18 const int INF = 0x3f3f3f3f;
19 const int NINF = 0xc0c0c0c0;
20 const ll mod=1e9+9;
21 int dp[MAXN];
22 int a[20];
23 int fibo(int v)
24 {
25     if(a[v]!=0) return a[v];
26     if(v<=2)
27     {
28         a[v]=v;
29         return a[v];
30     }
31     else a[v]=fibo(v-1)+fibo(v-2);
32     return a[v];
33  } 
34 
35 int main()
36 {
37     fibo(15);
38     
39     for(int i=0;i<=3000;i++)
40     {
41         dp[i]=1;
42     }
43     for(int i=2;i<=15;i++)
44     {
45         for(int j=a[i];j<=3000;j++)
46         {
47             dp[j]+=dp[j-a[i]];
48             dp[j]%=mod;
49         }
50     }
51     int t;cin>>t;
52     while(t--)
53     {
54         int m;cin>>m;
55         cout <<dp[m]<<endl;
56     }
57     return 0;
58     
59 }

 

多点搜的bfs

原文:https://www.cnblogs.com/Msmw/p/10585918.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!