双端队列deuqe+bfs

本蒟蒻了解到这道题居然是ACM-ICPC-WORLD-FINALS-2015的简化版之后 震惊了

了解一下 deque 双端队列 可以同时对队头队尾进行操作
原题可以在洛谷洛谷UVA1714上面写 或者到UVA官网提交

关键 : 预处理连续字符:通过预处理每个位置在四个方向上连续相同的字符,减少BFS过程中的无效搜索,提高搜索效率。

结构体和deque的组合运用 可以加强我们处理数据时 思考的逻辑性

原未简化版是有多组测试数据的 用此题解会wa 但是时间给了30000ms 很充足

注意 像这种 输入数据是一大推的字符的时候 要使用getchar()来消除换行符 这点和java里面的scanner.nextline 相同 当时 学Java的时候 也是被坑惨了

此题主要是deque和预处理的问题 详细请看代码

Code:
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <deque>
  4. #include <cstring>
  5. #include <iostream>
  6. #define int long long //个人习惯 有备无患
  7. using namespace std;
  8. const int N = 10000 + 10;
  9. char f[60][60]; // 地图
  10. int r, c;
  11. char s[N]; // 目标字符串
  12. int l; // 目标字符串长度
  13. int vis[60][60]; // 访问状态数组,记录到达某个位置时目标字符串的索引
  14. int ds[55][55][4][3]; // 预处理数组,存储每个位置在每个方向上连续相同的字符的终点位置
  15. struct node {
  16. int x, y, d; // 坐标和目标字符串的当前索引
  17. int step; // 步数
  18. };
  19. int dx[4] = {0 , 0, 1, -1}; // x方向移动
  20. int dy[4] = {1, -1, 0 , 0}; // y方向移动
  21. int ans = 0x7ffffff; // 初始化答案为最大值
  22. //void print(int x) {
  23. // for(int i = 0 ;i < x; i++) printf("%c",s[i]);
  24. // printf(" ");
  25. //}
  26. // 预处理函数,计算每个位置在每个方向上连续相同的字符的终点位置
  27. void pre() {
  28. for(int i = 1; i <= r; i++) {
  29. for(int j = 1; j <= c; j++) {
  30. for(int k = 0; k < 4; k++) {
  31. int x = i, y = j;
  32. while(f[x][y] == f[i][j]) {
  33. x += dx[k];
  34. y += dy[k];
  35. if(x < 0 || y < 0) break;
  36. if(!(x > 0 && x <= r && y >0 && y <= c)) break;
  37. }
  38. if(x > 0 && x <= r && y >0 && y <= c) {
  39. ds[i][j][k][0] = x;
  40. ds[i][j][k][1] = y;
  41. }
  42. }
  43. }
  44. }
  45. }
  46. void bfs() {
  47. deque <node> q;
  48. q.push_back((node){1,1,0,0}); // 起始位置入队
  49. while(q.size()) {
  50. int x = q.front().x;
  51. int y = q.front().y;
  52. int d = q.front().d;
  53. int step = q.front().step;
  54. q.pop_front();
  55. // 当前字符匹配目标字符串,更新步数和索引
  56. if(s[d] == f[x][y]) {
  57. int cnt = 0;
  58. int p = d;
  59. while(f[x][y] == s[p]) {
  60. cnt++;
  61. p++;
  62. }
  63. d += cnt;
  64. step += cnt;
  65. q.push_front((node){x,y,d,step}); // 重新入队
  66. }
  67. // 所有字符匹配完成,输出步数
  68. if(d == l + 1) {
  69. printf("%lld",step);
  70. return;
  71. }
  72. // 遍历四个方向,更新队列
  73. for(int i = 0; i < 4; i++) {
  74. int xx = ds[x][y][i][0];
  75. int yy = ds[x][y][i][1];
  76. if(xx > 0 && xx <= r && yy > 0 && yy <= c && vis[xx][yy] < d) {
  77. vis[xx][yy] = d;
  78. q.push_back((node){xx,yy,d,step + 1});
  79. }
  80. }
  81. }
  82. }
  83. signed main() {
  84. scanf("%lld %lld",&r,&c);
  85. getchar(); // 吸收换行符
  86. for(int i = 1; i <= r; i++) {
  87. for(int j = 1; j <= c; j++) {
  88. f[i][j] = getchar();
  89. }
  90. getchar(); // 吸收换行符
  91. }
  92. scanf("%s",s); // 读取目标字符串
  93. pre(); // 预处理
  94. l = strlen(s); // 获取字符串长度
  95. s[l] = '*';
  96. memset(vis,-1,sizeof(vis)); // 初始化访问状态数组
  97. bfs();
  98. return 0;
  99. }
点赞(0)
 

9.9 分

1 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论