双端队列deque+bfs--[信息学奥赛一本通T1452-Keyboarding] 原题变形：ACM-ICPC-WORLD-FINALS-2015

149 阅读 0 评论 0 点赞

原题链接：信息学奥赛一本通T1452-Keyboarding

# 双端队列deuqe+bfs
###### 本蒟蒻了解到这道题居然是ACM-ICPC-WORLD-FINALS-2015的简化版之后 震惊了

了解一下 deque 双端队列 可以同时对队头队尾进行操作
原题可以在洛谷[洛谷UVA1714](https://www.luogu.com.cn/problem/UVA1714 "洛谷UVA1714")上面写 或者到UVA官网提交

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

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

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

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

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

##### Code:
```cpp
#include <cstdio>
#include <algorithm>
#include <deque>
#include <cstring>
#include <iostream>
#define int long long //个人习惯 有备无患
using namespace std;

const int N = 10000 + 10;

char f[60][60]; // 地图
int r, c; 
char s[N]; // 目标字符串
int l; // 目标字符串长度

int vis[60][60]; // 访问状态数组，记录到达某个位置时目标字符串的索引
int ds[55][55][4][3]; // 预处理数组，存储每个位置在每个方向上连续相同的字符的终点位置

struct node {
    int x, y, d; // 坐标和目标字符串的当前索引
    int step; // 步数
};
int dx[4] = {0 , 0, 1, -1}; // x方向移动
int dy[4] = {1, -1, 0 , 0}; // y方向移动
int ans = 0x7ffffff; // 初始化答案为最大值

//void print(int x) {
//    for(int i = 0 ;i < x; i++) printf("%c",s[i]);
//    printf("   ");
//}

// 预处理函数，计算每个位置在每个方向上连续相同的字符的终点位置
void pre() {
    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= c; j++) {
            for(int k = 0; k < 4; k++) {
                int x = i, y = j;
                while(f[x][y] == f[i][j]) {
                    x += dx[k];
                    y += dy[k];
                    if(x < 0 || y < 0) break;
                    if(!(x > 0 && x <= r && y >0 && y <= c)) break;
                }
                if(x > 0 && x <= r && y >0 && y <= c) {
                    ds[i][j][k][0] = x;
                    ds[i][j][k][1] = y;
                }
            }
        }
    }
}

void bfs() {
    deque <node> q;
    q.push_back((node){1,1,0,0}); // 起始位置入队

while(q.size()) {
        int x = q.front().x;
        int y = q.front().y;
        int d = q.front().d;
        int step = q.front().step;
        q.pop_front();

// 当前字符匹配目标字符串，更新步数和索引
        if(s[d] == f[x][y]) {
            int cnt = 0;
            int p = d;
            while(f[x][y] == s[p]) {
                cnt++;
                p++;
            }
            d += cnt;
            step += cnt;
            q.push_front((node){x,y,d,step}); // 重新入队
        }
        // 所有字符匹配完成，输出步数
        if(d == l + 1) {
            printf("%lld",step);
            return;
        }
        // 遍历四个方向，更新队列
        for(int i = 0; i < 4; i++) {
            int xx = ds[x][y][i][0];
            int yy = ds[x][y][i][1];
            if(xx > 0 && xx <= r && yy > 0 && yy <= c && vis[xx][yy] < d) {
                vis[xx][yy] = d;
                q.push_back((node){xx,yy,d,step + 1});
            }
        }
    }
}

signed main() {
    scanf("%lld %lld",&r,&c);
    getchar(); // 吸收换行符
    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= c; j++) {
            f[i][j] = getchar(); 
        }
        getchar(); // 吸收换行符
    }
    scanf("%s",s); // 读取目标字符串
    pre(); // 预处理
    l = strlen(s); // 获取字符串长度
    s[l] = '*'; 
    memset(vis,-1,sizeof(vis)); // 初始化访问状态数组
    bfs(); 
	
    return 0;
}
```

0.0分

1 人评分

本文分类：题解列表
浏览次数：149 次浏览
发布日期：2024-09-26 20:48:07
本文链接：https://blog.dotcpp.com/a/106477

上一篇 > java与c++数据类型占用内存对比
下一篇 > [编程入门]最大公约数与最小公倍数最简单最明白的方法

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

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

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

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

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

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

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

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

双端队列deque+bfs--[信息学奥赛一本通T1452-Keyboarding] 原题变形：ACM-ICPC-WORLD-FINALS-2015

评论列表共有 0 条评论

发表评论取消回复

双端队列deque+bfs--[信息学奥赛一本通T1452-Keyboarding] 原题变形：ACM-ICPC-WORLD-FINALS-2015

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复