补题 ICPC新疆省赛 F题 Palindrome Square

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

There is an $n \times m$ square grid graph with each square containing a lowercase letter.

Alice wants to transform the grid graph into an elegant one where each row and column forms a palindrome string.

Alice can change a letter on the grid graph to the next or last letter in the lexicographical order by spending one energy. For instance, the next letter of ‘e’ is ‘f’, and the last letter of ‘e’ is ‘d’.

Specially, the last letter of ‘a’ is ‘z’, and the next letter of ‘z’ is ‘a’.

Alice wants to know the minimum energy required to transform the grid graph into an elegant one.

输入描述

The first line contains two integers $n$ $(1 \leq n \leq 1000)$ and $m$ $(1 \leq m \leq 1000)$ separated by a space.

The following $n$ lines, each contains a string of length $m$ consisting of lowercase letters.

输出描述

An integer representing the minimum energy required to transform the grid graph into an elegant one.

示例1

输入

1
2
3
2 2
ab
cd

输出

1
4

示例2

输入

1
2
3
2 3
aaa
zzz

输出

1
3

题解

题目解析

卡在某个地方了= =,又找了之前的大佬帮我解决了.

这道题怎么说呢,算是个暴力吧?解题思路是这样的:

设一点的坐标为 $(x,y)$ ,那么与之对称的两个点则记为 $(dx,y)$ , $(x,dy)$ ,那么如果在以 $(dx,y)$ 为点的坐标,那么在这三个对称点的基础上又多了一个点 $(dx,dy)$ .因为这是回文串,根据回文串的性质那么很容易的.我们得到相应的一个结论:这四个点的字符必须相同才能对称.

有了这个条件,我们就可以进一步考虑了.接着就是另一个问题:这四个字符变成哪个才可以使得代价最小?(我在这里出了差错,以为变成已经存在的字符才最小)事实上,我们需要枚举26个字母,分别判断哪个最小.

接着我们需要把这些都遍历一遍,由于中心必是对称的,所以中心的字母一定不用变换(如果是奇数的话).这样遍历的话,每个点会遍历四次(除了中心点,但是之前说了,中心点永远是0代价)所以我们需要将结果除以4.这样我们就得到了最终答案.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;

const int MAXN = 1010;
string s[MAXN];

int backjudege(char a,char b){//判断从a字符到b字符的最小代价
    int ans = abs(a-b);
    return min(ans,26-ans);//因为可以z->a走所以需要判断一下,别绕远道.
}

int backmin(char dx,char dy,char sx,char sy){
    int minn = 0x3f3f3f3f;
    for(char i='a';i<='z';i++)//遍历a->z哪个可以得到最小值
        minn = min(minn,backjudege(dx,i)+backjudege(dy,i)+backjudege(sx,i)+backjudege(sy,i));
    return minn;
}

int main(){
    int n,m;
    ll ans = 0;
    cin >> n >> m;
    for(int i=0;i<n;i++) cin >> s[i];
    for(int i=0;i<n;i++)
    	for(int j=0;j<m;j++)
    		ans += backmin(s[i][j],s[i][m-j-1],s[n-i-1][j],s[n-i-1][m-j-1]);
    cout << ans / 4;
    return 0;
}