信息学奥赛一本通T1452：Keyboarding

【题目描述】

给定一个 r 行 c 列的在电视上的“虚拟键盘”，通过「上，下，左，右，选择」共 555 个控制键，你可以移动电视屏幕上的光标来打印文本。一开始，光标在键盘的左上角，每次按方向键，光标总是跳到下一个在该方向上与当前位置不同的字符，若不存在则不移动。每次按选择键，则将光标所在位置的字符打印出来。

现在求打印给定文本（要在结尾打印换行符）的最少按键次数。

【输入】

第一行输入 r,c。

接下来给出一个 r×c 的键盘，包括大写字母，数字，横线以及星号（星号代表 Enter 换行）。

最后一行是要打印的文本串 S，SSS 的长度不超过 10000。

【输出】

输出打印文本（包括结尾换行符）的最少按键次数。保证一定有解。

【输入样例】

输入样例1

2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ

输入样例2

5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015

输入样例3

6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB

【输出样例】

输出样例1

19

输出样例2

160

输出样例3

7

思路：

很容易想到是 BFS，但直接用 BFS 来会 TLE，因此我们需要进行优化

考虑对后置点进行优化，我们知道，通过 BFS 到达的点，如果之前被访问过，那么肯定之前访问的步数最小，因此在 BFS 的过程中，可以记录打印出的字符的位置，这样一来，如果一个后置点的位置要小于前置点，那么无论如何距离也不可能更小，这样就不用向下进行扩展了，同时，如果后置点的位置更大，那么就将当前点的位置赋给后置点

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair<int,int>
LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; }
LL multMod(LL a,LL b,LL mod){ a%=mod; b%=mod; LL res=0; while(b){if(b&1)res=(res+a)%mod; a=(a<<=1)%mod; b>>=1; } return res%mod;}
LL quickMultPowMod(LL a, LL b,LL mod){ LL res=1,k=a; while(b){if((b&1))res=multMod(res,k,mod)%mod; k=multMod(k,k,mod)%mod; b>>=1;} return res%mod;}
LL quickPowMod(LL a,LL b,LL mod){ LL res=1; while(b){if(b&1)res=(a*res)%mod; a=(a*a)%mod; b>>=1; } return res; }
LL getInv(LL a,LL mod){ return quickPowMod(a,mod-2,mod); }
LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); }
LL LCM(LL x,LL y){ return x/GCD(x,y)*y; }
const double EPS = 1E-6;
const int MOD = 1000000000+7;
const int N = 50+5;
const int dx[] = {-1,0,0,1,1,-1,1,1};
const int dy[] = {0,-1,1,0,-1,1,-1,1};
using namespace std;

struct Node {
    int x, y; //横纵坐标
    int op, step; //选择次数，按键次数
    Node() {}
    Node(int x, int y, int op, int step) : x(x), y(y), op(op), step(step) {}
};
struct Next{//下一步的坐标
    int x, y;
    Next() {}
    Next(int x,int y):x(x),y(y){}
}nxt[N][N][4];
int n, m;
char str[N][N], s[10000+5];
int G[N][N];
int vis[N][N];
void BFS(int len) {
    memset(vis, -1, sizeof(vis));
    queue<Node> Q;
    Q.push(Node(1, 1, 0, 0));
    while (!Q.empty()) {
        Node now = Q.front();
        Q.pop();
        int x = now.x, y = now.y;
        int op = now.op, step = now.step;
        if (str[x][y] == s[op + 1]) {
            Q.push(Node(x, y, op + 1, step + 1));
            if(op+1==len){
                printf("%d\n", step + 1);
                return;
            }
        }
        else{
            for (int i = 0; i < 4; i++) {
                int nx = nxt[x][y][i].x, ny = nxt[x][y][i].y;
                if(nx==0)
                    continue;
                if(vis[nx][ny]<op){
                    vis[nx][ny] = op;
                    Q.push(Node(nx, ny, op, step + 1)) ;
                }
            }
        }
    }
}
int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 1; i <= n; i++)
            scanf("%s", str[i] + 1);
        scanf("%s", s + 1);
        int len = 1;
        while(s[len])
            len++;
        s[len] = '*';
        //预处理判断能走的地方
        for (int i = 1; i <= n; i++) { //枚举行
            for (int j = 1; j <= m; j++) { //枚举列
                for (int k = j - 1; k >= 1; k--) { //向上
                    if (str[i][j] != str[i][k]) {
                        nxt[i][j][0] = Next(i, k);
                        break;
                    }
                }
                for (int k = j + 1; k <= m; k++) { //向下
                    if (str[i][j] != str[i][k]) {
                        nxt[i][j][1] = Next(i, k);
                        break;
                    }
                }
                for (int k = i - 1; k >= 1; k--) { //向左
                    if (str[i][j] != str[k][j]) {
                        nxt[i][j][2] = Next(k, j);
                        break;
                    }
                }
                for (int k = i + 1; k <= n; k++) { //向右
                    if (str[i][j] != str[k][j]) {
                        nxt[i][j][3] = Next(k, j);
                        break;
                    }
                }
            }
        }
        BFS(len);
     }
    return 0;
}

信息学奥赛一本通T1452：深搜的剪枝技巧 Keyboarding 归属于 深搜的剪枝技巧，更多同类题解源程序见：深搜的剪枝技巧 和 Keyboarding