链接
题解链接:
题意：
给定n*m的字母矩阵。
从左上角到右下角的路径中有多少条是回文。
思路：
显然是要从头尾同时dp的，路径1是从左上角到第j行，，路径2是从右下角到第k行
dp[i][j][k] 表示路径长度为i，路径1从左上角到第j行,路径2从右下角到第k行，且路径1和2是匹配的方法数。
对于路径1、2合并时要分一下奇偶。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include <stdio.h> #include <iostream> #include <algorithm> #include <sstream> #include <stdlib.h> #include <string.h> #include <limits.h> #include <vector> #include <string> #include <time.h> #include <math.h> #include <iomanip> #include <queue> #include <stack> #include <set> #include <map> const int inf = 1e9;const double eps = 1e-8;const double pi = acos(-1.0);template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x < 0) { putchar('-'); x = -x; }if (x > 9) pt(x / 10);putchar(x % 10 + '0');}using namespace std;const int N = 520;const int mod = 1e9 + 7;typedef long long ll;typedef pair<int, int> pii;void add(int &x, int y) {x += y;if (x >= mod)x -= mod;}int mul(int x, int y) {x = (ll)x*y%mod;return x;}int n, m;char s[N][N];vector<pii>G[1005];int step[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 }, dis[N][N];bool inmap(int x, int y) {return 1 <= x&&x <= n && 1 <= y&&y <= m;}void bfs() {queue<int>qx, qy;qx.push(1); qy.push(1);dis[1][1] = 1;while (!qx.empty()) {int ux = qx.front(), uy = qy.front();G[dis[ux][uy]].push_back({ ux, uy });qx.pop(); qy.pop();for (int i = 0; i < 2; i++) {int vx = ux + step[i][0], vy = uy + step[i][1];if (inmap(vx, vy) && !dis[vx][vy]) {dis[vx][vy] = dis[ux][uy] + 1;qx.push(vx); qy.push(vy);}}}}int dp[2][N][N];int main() {rd(n); rd(m);for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);if (s[1][1] != s[n][m]) { puts("0"); return 0; }s[0][1] = 'a'; s[1][0] = 'z' + 1;s[n + 1][m] = 'a'; s[n][m + 1] = 'z' + 1;bfs();int cur = 0, old = 1;memset(dp[cur], 0, sizeof dp[cur]);dp[cur][1][n] = 1;int l = 1, r = n + m – 1;for (int i = 2; i <= (n + m) / 2; i++, l++, r–){swap(cur, old);memset(dp[cur], 0, sizeof dp[cur]);for (auto u : G[l]){int x = u.first, y = u.second;for (auto v : G[r]){int tx = v.first, ty = v.second;if (dp[old][x][tx] == 0)continue;for (int a = 0; a < 2; a++){int ux = x + step[a][0], uy = y + step[a][1];if (!inmap(ux, uy))continue;for (int b = 2; b < 4; b++){int vx = tx + step[b][0], vy = ty + step[b][1];if (!inmap(vx, vy))continue;if (s[ux][uy] != s[vx][vy])continue;add(dp[cur][ux][vx], dp[old][x][tx]);}}}}}int ans = 0;if ((n + m) & 1){for (int i = 1; i <= n; i++)add(ans, dp[cur][i][i]);for (int i = 1; i <= n; i++)add(ans, dp[cur][i][i + 1]);}else {for (int i = 1; i <= n; i++)add(ans, dp[cur][i][i]);}pt(ans);return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
世上最累人的事，莫过於虚伪的过日子
