首页 > 代码库 > 回文路径

回文路径

2024-08-17 12:11:45   219人阅读

约翰有一片牧场，这片牧场可以分为 N ×N 个方格，每个方格里有一个英文字母表示它的类型。 贝西要从牧场的左上角出发，一路向右或向下移动到牧场的右下角。贝西希望她的足迹能组成一条回 文。所谓回文，就是翻转后仍然保持不变的字符串。请问贝西有多少种走法可以使得她的足迹组成回 文？注意两条不同的路径可能会构成了同样的回文，这样的话这两条路径都要作为不同的方案数计入答 案。由于结果可能会很大，输出答案模 109 + 7 的余数即可

f[d][x][xx]:位于(x,y)(xx,yy),距离对角线d,y=(n-1)-x-d,yy=(n-1)-y+d xx在下，x在上

f[d][x][xx]=    f[d][x][xx] = f[d-1][x][xx]  +f[d-1][x+1][xx]+f[d-1][x][xx-1]+f[d-1][x+1][xx-1];或0（两点不相等）

这个代码不一定对

#include<iostream>
#include<cstdio>
using namespace std;
int n; 
char board[510][510];
int f[510][510][510];

bool inrange(int y,int yy)
{
	return (y>=0&&yy>=0&&y<n&&yy<n);
}

int main()
{
	cin>>n;
	for(int i=0;i<n;i++) 
		for(int j=0;j<n;j++) 
		  cin>>board[i][j];
	for(int i=0;i<n;i++) 
	  f[0][i][i] = 1;
	for(int d=1;d<n;d++)
		for(int x=n-1;x>=0;x--)
			for(int xx=0;xx<n;xx++)
			{	
				int y=n-1-x-d,yy=n-1-xx+d;
				if(!inrange(y,yy)||board[x][y]!=board[xx][yy])
				  {f[d][x][xx]=0;continue;}
				if(inrange(x+1,xx-1))
				f[d][x][xx] = 
				      f[d-1][x][xx]
					 +f[d-1][x+1][xx]
					 +f[d-1][x][xx-1]
					 +f[d-1][x+1][xx-1];
			}
	cout<<f[n-1][0][n-1]<<endl;
	return 0;
}

 


                  

回文路径


联系
我们