双端队列deuqe+bfs

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

了解一下 deque 双端队列 可以同时对队头队尾进行操作

关键 ： 预处理连续字符：通过预处理每个位置在四个方向上连续相同的字符，减少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;
}