2022绍兴市初中组编程比赛-----问题 D: 回文路径(path) 题解

题目

问题 D: 回文路径(path)

题目描述

给你一个 n*n 的棋盘，每个格子里有一个小写英文字母。刚开始有个棋子在棋盘的左上角(1,1)，每次你把它可以往下或往右移动一格，最终你需要把棋子移动到棋盘的右下角(n,n)。一条路径是合法的当且仅当棋子途经的字母依次连接起来是个回文字符串。
棋盘刚开始可能不存在这么一条路径，但是你可以对棋盘使用魔法。每次使用魔法可以将某个格子里的字母修改成任意小写英文字母。由于法力很珍贵，所以你需要求出最少使用多少次魔法才会存在合法路径。

输入

第一行一个整数 n；
接下来 n 行，每行一个长度为 n 的字符串。

输出

一行一个整数，表示答案。

样例输入

5
final
phase
level
judge
light

样例输出

2

提示

样例输入1
3
alb
aba
awa
样例输出2
0
样例1：把(1,1)的f改成t、(2,1)的p改成e，路径(1,1)->(2,1)->(3,1)->(3,2)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5) 途经的字母依次连接起来的字符串为 “televelet”。
样例2：路径(1,1)->(2,1)->(2,2)->(2,3)->(3,3) 途经的字母依次连接起来的字符串为“aabaa”。
【数据范围约定】
对于10%的数据，n≤2；
对于30%的数据，n≤10；
对于50%的数据，n≤50；
对于80%的数据，n≤200；
对于所有数据，1≤n≤500，棋盘里所有字符都是小写英文字母。
【提示】
请注意内存限制。如果你开的数组超出内存限制可能会导致你的代码直接获得0分！
保险起见，你开的 int 数组总大小不得超过3×10^7。

题解

可以用两个方向走，一个在起点，一个在终点，如果不同就用魔法，最后两个方向相遇时字符串结果一样就可以结束了。
优化看代码。

#include <bits/stdc++.h>
using namespace std;
int n,f[2][510][510],sum;
char g[510][510];
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%d",&n);
    for (int i = 1; i <= n; i++){
        scanf("%s",g[i]+1);
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            f[1][i][j] = n+1;
        }
    }
    sum = n+1;
    if (g[1][1] == g[n][n]) f[1][1][n] = 0;
    else  f[1][1][n] = 1;
    for (int k = 2; k <= n; k++){
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) f[k&1][i][j] = n+1;
        for (int x1 = 1; x1 <= n; x1++){
            int y1 = k+1-x1;
            if (y1 < 1 || y1 > n)     continue;
            for (int x2 = 1; x2 <= n; x2++){
                int y2 = 2*n+1-k-x2;
                if (y2 < 1 || y2 > n) continue;
                int v = 1;
                if (g[x1][y1] == g[x2][y2]) v = 0;
                if (x1-1 >= 1 && x2+1 <= n) f[k&1][x1][x2] = min(f[k&1][x1][x2],f[(k-1)&1][x1-1][x2+1]);
                if (x1-1 >= 1 && y2+1 <= n) f[k&1][x1][x2] = min(f[k&1][x1][x2],f[(k-1)&1][x1-1][x2]);
                if (y1-1 >= 1 && x2+1 <= n) f[k&1][x1][x2] = min(f[k&1][x1][x2],f[(k-1)&1][x1][x2+1]);
                if (y1-1 >= 1 && y2+1 <= n) f[k&1][x1][x2] = min(f[k&1][x1][x2],f[(k-1)&1][x1][x2]);
                f[k&1][x1][x2] += v;
                if (x1 == x2 && y1 == y2) sum = min(sum,f[k&1][x1][x2]);
            }
        }
    }
    printf("%d",sum);
    return 0;
}