yxy

用户名：dotcpp0787179

访问量：445

签　名：

竞赛交流论坛： blog.qzcy2.top 欢迎来撩！

等　　级
排　　名	1030
经　　验	3291
参赛次数	1
文章发表	23
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

我不会

TA的其他文章

[食物链] 并查集 - NOI2001 提高组
浏览：22

[金银岛]自定义排序优先'均权'最大--我看题解都太复杂辣
浏览：48

杀到这九天十地无人敢称尊,直到身边再无一人能陪我征战,叶天帝不过如此
浏览：23

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （Java代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

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

　　作者: yxy　　　　发表时间：2024-09-26 20:48:07 浏览：30　|　评论：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 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

yxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （Java代码）

人见人爱A+B （C语言代码）

C语言训练-舍罕王的失算（C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言训练-谁家孩子跑最慢* （C语言代码）

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

评论区

精彩推荐

Biggest Number （C++代码）回溯法

高精度加法（C++代码）（大数加法）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

字符串比较（C语言代码）答案错误？？？？

输出正反三角形（C语言代码）格式错误！！！

简单的a+b （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

【矩阵】（C++代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

yxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （Java代码）

人见人爱A+B （C语言代码）

C语言训练-舍罕王的失算 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言训练-谁家孩子跑最慢* （C语言代码）

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

评论区

精彩推荐

Biggest Number （C++代码）回溯法

高精度加法 （C++代码）（大数加法）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

字符串比较 （C语言代码）答案错误？？？？

输出正反三角形 （C语言代码）格式错误！！！

简单的a+b （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）万恶的long long

【矩阵】 （C++代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言训练-舍罕王的失算（C语言代码）

　　评论区

高精度加法（C++代码）（大数加法）

字符串比较（C语言代码）答案错误？？？？

输出正反三角形（C语言代码）格式错误！！！

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

【矩阵】（C++代码）