洛谷 P1141 01迷宫题解

对于60\%60%的数据,n 100,m 100n 100,m 100;

对于100\%100%的数据,n 1000,m 100000n 1000,m 100000。

先介绍采用裸的bfs,当然不能满分。再介绍如何优化得到满分。

 1 #include iostream 
 2 #include stdio.h 
 3 #include math.h 
 4 #include algorithm 
 5 #include string.h 
 7 using namespace std;
 9 struct node
11 int x, y;
12 };
13 node q[1000005]; 
15 const int maxn = 1005;
16 int n, m, a, b, c, d, front, last, step; 
17 int pos[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
18 char abc[maxn][maxn]; // 存储输入的矩阵信息 
19 bool vis[maxn][maxn]; // 是否已经遍历过该点 
22 void bfs
24 node now;
25 now.x = a;
26 now.y = b;
27 vis[a][b] = 1;
29 front = last = 0;
30 q[last] = now;
31 last++;
32 while
34 now = q[front++];
35 for
37 int nx = now.x + pos[i][0]; 
38 int ny = now.y + pos[i][1]; 
39 if 
43 vis[nx][ny] = true;
44 q[last].x = nx;
45 q[last].y = ny;
46 step++;
47 last++;
49 } 
53 int main
55 cin n m;
56 for
58 for
60 cin abc[i][j];
63 for
65 cin a b;
66 step = 1;
67 bfs;
68 cout step endl;
69 memset);
71 return 0;
72 }

裸的bfs并没有什么技巧,只是注意q队列不要太小,太小会导致wa。这个代码会有3个测试点tle。

 之所以会出现tle,主要是有很多次询问,每次询问都做了一次bfs,要优化代码就要减少bfs的次数。注意到这样一个事实:如果迷宫中存在连通块,则连通块中各格子到其他格子的个数是相同的。而求连通块本身就是利用bfs实现的。下面就是利用连通块进行优化的代码。

 1 #include iostream 
 2 #include stdio.h 
 3 #include math.h 
 4 #include algorithm 
 5 #include string.h 
 7 using namespace std;
 9 struct node
11 int x, y;
12 };
13 node q[1000005];
14 int cnt[1000005];
16 const int maxn = 1005;
17 int n, m, a, b, c, d, front, last, step, num; 
18 int pos[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
19 char abc[maxn][maxn]; // 存储输入的矩阵信息 
20 bool vis[maxn][maxn]; // 是否已经遍历过该点
21 int map[maxn][maxn]; // 用于对连通块染色 
24 void bfs
26 node now, next;
27 now.x = a;
28 now.y = b;
29 map[a][b] = num;
30 vis[a][b] = 1;
31 step = 1;
33 front = last = 0;
34 q[last] = now;
35 last++;
36 while
38 now = q[front++];
39 for
41 int nx = now.x + pos[i][0]; 
42 int ny = now.y + pos[i][1]; 
43 if 
47 vis[nx][ny] = true;
48 q[last].x = nx;
49 q[last].y = ny;
50 map[nx][ny] = num;
51 step++;
52 last++;
54 } 
56 cnt[num] = step;
57 num++;
60 int main
62 cin n m;
63 for
65 for
67 cin abc[i][j];
70 num = 1;
71 for
73 cin a b;
74 if 
76 bfs; 
77 } 
78 cout cnt[map[a][b]] endl;
80 return 0;
81 }

其中的map数组是用来存储连通块的染色信息的。如果格子对应的map数据为0,说明没有做过bfs。cnt数组存储着每个连通块所对应的格子个数。经过这次优化,就可以ac了。

 

新闻聚焦
猜你喜欢
热门推荐
  • 选择排序的理解

    选择排序的理解

    .........

    2019-08-13 来源: 浏览:47 次

    分享
  • C++ 单例模式(懒汉、饿汉模式)

    C++ 单例模式(懒汉、饿汉模式)

    // 饿汉模式的关键:初始化即实例化singelton *singelton::single = new singelton;int singelton::m_.........

    2019-08-13 来源: 浏览:89 次

    分享
  • 洛谷 P1141 01迷宫题解

    洛谷 P1141 01迷宫题解

    对于60\%60%的数据,n 100,m 100n 100,m 100;对于100\%100%的数据,n 1000,m 100000n 1000,m 10000.........

    2019-08-13 来源: 浏览:57 次

    分享
  • Java连载12

    Java连载12

    一、集成开发环境1.什么是集成开发环境集成开发环境可以使软件开发变得更简单没有ide工具:i.需要安装jdk,需要配置环境变量;需要手动的将java源文件编译生.........

    2019-08-13 来源: 浏览:43 次

    分享
  • c#使用SoundPlayer播放wav格式音频

    c#使用SoundPlayer播放wav格式音频

    1.引用system.media名称空间下的类soundplayer soundplayer player = new soundplayer;2.方法.........

    2019-08-08 来源: 浏览:15 次

    分享
  • bin文件夹下的某个dll总是自动刷新为

    bin文件夹下的某个dll总是自动刷新为

    如上图所示,一般这种问题都是dll版本和配置文件中的dll版本对应不上才引起的,可以通过替换对应版本的dll或者修改配置文件中的版本号即可。然而我的情况是:修复...

    2019-08-08 来源: 浏览:48 次

    分享
  • WeihanLi.Npoi 导出支持自定义列内容啦

    WeihanLi.Npoi 导出支持自定义列内容啦

    之前也有网友给提出过希望列合并或者自定义列内容的 issue 或请求,起初因为自己做 weihanli.npoi 这个扩展的最初目的是导入导出的简单化,使用这个.........

    2019-08-08 来源: 浏览:51 次

    分享
  • 1. mvc 树形控件tree + 表格jqgrid 显示界

    1. mvc 树形控件tree + 表格jqgrid 显示界

    [{"id":"1","text":"系统管理","value":"1","parentnodes":"0","showcheck":false,"isexpa.........

    2019-08-08 来源: 浏览:25 次

    分享
换一换
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。