P6473 - 回文路径(path)

内存限制：256 MB 时间限制：2 S

题面：传统评测方式：文本比较上传者：

提交：0 通过：0

给你一个 n*n 的棋盘，每个格子里有一个小写英文字母。刚开始有个棋子在棋盘的左上角(1,1)，每次你把它可以往下或往右移动一格，最终你需要把棋子移动到棋盘的右下角(n,n)。一条路径是合法的当且仅当棋子途经的字母依次连接起来是个回文字符串。

棋盘刚开始可能不存在这么一条路径，但是你可以对棋盘使用魔法。每次使用魔法可以将某个格子里的字母修改成任意小写英文字母。由于法力很珍贵，所以你需要求出最少使用多少次魔法才会存在合法路径。

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

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

5
final
phase
level
judge
light

样例输入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。

2022 绍兴初中

6473: 回文路径(path)

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签