列表

详情

NC252116. Palindrome Square

描述

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

输入: 

2 2
ab
cd

输出: 

4

示例2

输入: 

2 3
aaa
zzz

输出: 

3

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 39ms, 内存消耗: 2344K, 提交时间: 2023-05-24 15:06:18 

#include <iostream>
#include <cstdio>
#define abs(x) (x>0?(x):-(x))
using namespace std;
int n,m,a,b,c,d,x,y,ans;
char str[1234][1234];
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
		scanf("%s",str[i]+1);
	for (int i=1;i<=(n+1)/2;++i)
		for (int j=1;j<=(m+1)/2;++j)
		{
			a=str[i][j]-97;
			b=str[n-i+1][j]-97;
			c=str[n-i+1][m-j+1]-97;
			d=str[i][m-j+1]-97;
			y=1000;
			if (i==n-i+1 && j==m-j+1)	continue;
			for (int ch=0;ch<26;++ch)
			{
				x=min(abs(a-ch),26-abs(a-ch))+min(abs(b-ch),26-abs(b-ch))
				+min(abs(c-ch),26-abs(c-ch))+min(abs(d-ch),26-abs(d-ch));
				y=min(x,y);
			}
			if (i==n-i+1 || j==m-j+1)	y/=2;
			//cout<<i<<' '<<j<<' '<<y<<endl;
			ans+=y;
		}
	cout<<ans<<endl;
	return 0;
}

pypy3 解法, 执行用时: 1747ms, 内存消耗: 28812K, 提交时间: 2023-06-19 09:37:26 

n,m = map(int,input().split())
mp = []
for i in range(n):
    mp.append(input())
def change(a,b):
    aa=abs(ord(b) - ord(a))
    return min(aa, 26-aa)
ans = 0
for i in range(n//2):
    for j in range(m//2):
        a,b,c,d = mp[i][j],mp[i][m-1-j],mp[n-1-i][j],mp[n-1-i][m-1-j]
        ans += min(change(a,b)+change(a,c)+change(a,d),change(a,b)+change(b,c)+change(b,d),
                  change(a,c)+change(b,c)+change(c,d),change(a,d)+change(b,d)+change(c,d))
if n%2:
    for i in range(m//2):
        a,b = mp[n//2][i],mp[n//2][m-1-i]
        ans += change(a,b)
if m%2:
    for i in range(n//2):
        a,b = mp[i][m//2],mp[n-1-i][m//2]
        ans += change(a,b)
print(ans)

Python3 解法, 执行用时: 1793ms, 内存消耗: 5616K, 提交时间: 2023-06-25 15:58:26 

n,m = map(int,input().split())
mp = []
for i in range(n):
    mp.append(input())
def change(a,b):
    aa=abs(ord(b) - ord(a))
    return min(aa, 26-aa)
ans = 0
for i in range(n//2):
    for j in range(m//2):
        a,b,c,d = mp[i][j],mp[i][m-1-j],mp[n-1-i][j],mp[n-1-i][m-1-j]
        ans += min(change(a,b)+change(a,c)+change(a,d),change(a,b)+change(b,c)+change(b,d),
                  change(a,c)+change(b,c)+change(c,d),change(a,d)+change(b,d)+change(c,d))
if n%2:
    for i in range(m//2):
        a,b = mp[n//2][i],mp[n//2][m-1-i]
        ans += change(a,b)
if m%2:
    for i in range(n//2):
        a,b = mp[i][m//2],mp[n-1-i][m//2]
        ans += change(a,b)
print(ans)

C++(clang++ 11.0.1) 解法, 执行用时: 86ms, 内存消耗: 1428K, 提交时间: 2023-05-28 20:35:58 

#include<iostream>
using namespace std;
const int N=1e3+10;
typedef long long LL;
int n,m;
char a[N][N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) cin>>a[i]+1;
	
	LL res=0;
	
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	 {
	 	int cnt=1e9;
	 	for(int z='a';z<='z';z++)
	 	{
	 		int ans=0;
	 		int d=abs(a[i][j]-z);
	 		ans+=min(d,26-d);
	 		d=abs(a[i][m-j+1]-z);
	 		ans+=min(d,26-d);
	 		d=abs(a[n-i+1][j]-z);
	 		ans+=min(d,26-d);
	 		d=abs(a[n-i+1][m-j+1]-z);
	 		ans+=min(d,26-d);
	 		cnt=min(cnt,ans);
		}
		res+=cnt;
	 }


     printf("%lld\n",res/4);
	return 0;
}

上一题

© 2024 nowcoder.com