双端队列deuqe+bfs
本蒟蒻了解到这道题居然是ACM-ICPC-WORLD-FINALS-2015的简化版之后 震惊了
了解一下 deque 双端队列 可以同时对队头队尾进行操作
原题可以在洛谷洛谷UVA1714上面写 或者到UVA官网提交
关键 : 预处理连续字符:通过预处理每个位置在四个方向上连续相同的字符,减少BFS过程中的无效搜索,提高搜索效率。
结构体和deque的组合运用 可以加强我们处理数据时 思考的逻辑性
原未简化版是有多组测试数据的 用此题解会wa 但是时间给了30000ms 很充足
注意 像这种 输入数据是一大推的字符的时候 要使用getchar()来消除换行符 这点和java里面的scanner.nextline 相同 当时 学Java的时候 也是被坑惨了
此题主要是deque和预处理的问题 详细请看代码
Code:
#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;
}
9.9 分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复