UVa 12295 Optimal Symmetric Paths

题目描述

你有一个nnn行nnn列的网格，每个单元格包含一个非零数字（111到999）。你需要从左上角(0,0)(0,0)(0,0)走到右下角(n−1,n−1)(n-1,n-1)(n−1,n−1)，每一步可以向上、下、左、右移动到相邻单元格（不能走对角线），并且不能重复访问同一个单元格。此外，路径必须关于从网格左下角到右上角的副对角线对称。下图展示了一个6×66 \times 66×6网格中的一条对称路径。

你的任务是，在所有合法对称路径中，找出数字和最小的路径有多少条？答案对1,000,000,0091,000,000,0091,000,000,009取模。

输入格式
最多252525个测试用例。每个测试用例以一个整数nnn（2≤n≤1002 \le n \le 1002≤n≤100）开始。接下来nnn行，每行包含nnn个非零数字（111-999）。输入以n=0n=0n=0结束。

输出格式
对每个测试用例，输出最优对称路径的数量，模1,000,000,0091,000,000,0091,000,000,009。

题目分析

对称性的理解

题目要求路径关于副对角线对称。副对角线是连接左下角(n−1,0)(n-1,0)(n−1,0)和右上角(0,n−1)(0,n-1)(0,n−1)的直线，其上的点满足i+j=n−1i + j = n-1i+j=n−1。

对称性意味着：如果路径经过点(i,j)(i,j)(i,j)，则它也必须经过其对称点(n−1−j, n−1−i)(n-1-j,\; n-1-i)(n−1−j,n−1−i)。特别地：

• 起点(0,0)(0,0)(0,0)的对称点是终点(n−1,n−1)(n-1,n-1)(n−1,n−1)。
• 终点(n−1,n−1)(n-1,n-1)(n−1,n−1)的对称点是起点(0,0)(0,0)(0,0)。
• 如果(i,j)(i,j)(i,j)在副对角线上（i+j=n−1i+j=n-1i+j=n−1），则对称点就是它本身。

因此，整条路径关于副对角线对称，我们可以只考虑副对角线及其左上方（即i+j≤n−1i+j \le n-1i+j≤n−1）的区域，另一半由对称性自动确定。

路径权重的计算

由于对称性，当路径经过(i,j)(i,j)(i,j)和它的对称点时，这两个单元格的数字都要计入总权重。但为了简化计算，我们可以预先定义一个对称权重矩阵cost[i][j]cost[i][j]cost[i][j]，表示如果路径经过(i,j)(i,j)(i,j)（从而必然经过对称点），应贡献的总数字和：

• 如果i+j=n−1i+j = n-1i+j=n−1（在副对角线上），则cost[i][j]=grid[i][j]cost[i][j] = grid[i][j]cost[i][j]=grid[i][j]。
• 否则，cost[i][j]=grid[i][j]+grid[n−1−j][n−1−i]cost[i][j] = grid[i][j] + grid[n-1-j][n-1-i]cost[i][j]=grid[i][j]+grid[n−1−j][n−1−i]。

注意：我们只对i+j≤n−1i+j \le n-1i+j≤n−1的区域定义costcostcost，因为i+j>n−1i+j > n-1i+j>n−1的区域是对称的，不需要重复计算。

问题转化

原问题转化为：在只允许访问i+j≤n−1i+j \le n-1i+j≤n−1的区域、且每一步只能向相邻单元格移动（不重复访问）的条件下，从(0,0)(0,0)(0,0)出发，到达副对角线上的任意一点(k,n−1−k)(k, n-1-k)(k,n−1−k)的最小总权重路径的数量。因为从(0,0)(0,0)(0,0)到(n−1,n−1)(n-1,n-1)(n−1,n−1)的对称路径必然经过副对角线上的某个点，并且由于对称性，路径在副对角线上的点“反射”后形成完整路径。

因此，我们只需要：

1. 求出从(0,0)(0,0)(0,0)到每个副对角线点(k,n−1−k)(k, n-1-k)(k,n−1−k)的最小总权重。
2. 找出这些最小权重中的最小值minValueminValueminValue。
3. 统计所有从(0,0)(0,0)(0,0)到副对角线点且总权重等于minValueminValueminValue的路径数量。

算法设计

步骤1：最短路径搜索

这是一个带有非负权重的网格图最短路径问题，可以使用Dijkstra\texttt{Dijkstra}Dijkstra算法。
我们只考虑区域i+j≤n−1i+j \le n-1i+j≤n−1，从(0,0)(0,0)(0,0)开始，更新到每个点的最短距离dist[i][j]dist[i][j]dist[i][j]，同时记录每个节点的前驱节点列表parentparentparent，用于后续统计路径数量。

步骤2：构建隐式图并统计路径数

得到所有点的最短距离后，我们构建一个隐式图：

• 每个网格点(i,j)(i,j)(i,j)对应一个节点，编号为i×n+ji \times n + ji×n+j。
• 对于每个节点vvv，遍历其前驱节点列表parent[v]parent[v]parent[v]，在图中添加一条有向边u→vu \to vu→v（uuu是vvv的前驱）。

这样，从起点(0,0)(0,0)(0,0)到任意节点vvv的所有最短路径就对应隐式图中从000到vvv的所有路径。

步骤3：记忆化搜索（DFS\texttt{DFS}DFS）计数

我们设dp[u]dp[u]dp[u]表示从节点uuu出发，到达任意一个最优副对角线节点（即distdistdist等于bestbestbest的副对角线节点）的最短路径数量。

初始化：

• 对于副对角线上的节点v=(k,n−1−k)v = (k, n-1-k)v=(k,n−1−k)，如果dist[v]=bestdist[v] = bestdist[v]=best，则dp[v]=1dp[v] = 1dp[v]=1（表示到达自身有一条路径）；否则dp[v]=0dp[v] = 0dp[v]=0。
• 其他节点dp[u]=−1dp[u] = -1dp[u]=−1（未计算）。

然后从起点000（对应(0,0)(0,0)(0,0)）开始进行记忆化DFS\texttt{DFS}DFS：
dp[u]=∑v∈g[u]dp[v]dp[u] = \sum_{v \in g[u]} dp[v]dp[u]=∑v∈g[u]​dp[v]，其中g[u]g[u]g[u]是uuu的后继节点列表（即隐式图中从uuu出发能到达的下一个节点）。

最终dp[0]dp[0]dp[0]即为所求的答案。

复杂度分析

• Dijkstra\texttt{Dijkstra}Dijkstra算法：网格有O(n2)O(n^2)O(n2)个节点，每个节点最多444条边。使用优先队列，时间复杂度O(n2log⁡n)O(n^2 \log n)O(n2logn)。
• 构建隐式图：遍历所有边，O(n2)O(n^2)O(n2)。
• 记忆化DFS\texttt{DFS}DFS：每个节点访问一次，O(n2)O(n^2)O(n2)。
  总时间复杂度O(n2log⁡n)O(n^2 \log n)O(n2logn)，在n≤100n \le 100n≤100时完全可行。

空间复杂度O(n2)O(n^2)O(n2)。

代码实现

// Optimal Symmetric Paths// UVa ID: 12295// Verdict: Accepted// Submission Date: 2025-12-25// UVa Run Time: 0.010s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=110;constintMOD=1000000009,INF=0x3f3f3f3f;constintdx[4]={1,-1,0,0},dy[4]={0,0,1,-1};intdist[MAXN][MAXN],grid[MAXN][MAXN],cost[MAXN][MAXN],dp[MAXN*MAXN];vector<int>g[MAXN*MAXN];// 隐式图的邻接表vector<int>parent[MAXN*MAXN];// 每个节点的最短路径前驱节点// 记忆化搜索：从节点 u 出发到达副对角线的最优路径数量intdfs(intu){intanswer=0;for(autov:g[u]){if(~dp[v])answer=(answer+dp[v])%MOD;elseanswer=(answer+dfs(v))%MOD;}returndp[u]=answer;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn;while(cin>>n&&n){// 读入网格for(inti=0;i<n;i++)for(intj=0;j<n;j++)cin>>grid[i][j];// 计算对称权重矩阵，仅考虑副对角线及其左上方区域for(inti=0;i<n;i++)for(intj=0;j<n;j++){if(i+j>=n)continue;// 忽略右下方区域intsi=n-1-j,sj=n-1-i;// 对称点坐标if(i+j==n-1)cost[i][j]=grid[i][j];// 副对角线上的点elsecost[i][j]=grid[i][j]+grid[si][sj];// 非对角线点，加上对称点权重}// Dijkstra 求最短路径memset(dist,0x3f,sizeofdist);for(inti=0;i<n*n;i++)parent[i].clear();dist[0][0]=cost[0][0];usingstate=tuple<int,int,int>;priority_queue<state,vector<state>,greater<state>>pq;pq.push({dist[0][0],0,0});while(!pq.empty()){auto[d,x,y]=pq.top();pq.pop();if(d>dist[x][y])continue;for(intdir=0;dir<4;dir++){intnx=x+dx[dir],ny=y+dy[dir];// 确保在网格内且位于副对角线左上方if(nx<0||nx>=n||ny<0||ny>=n||nx+ny>=n)continue;intnd=d+cost[nx][ny];if(nd<dist[nx][ny]){dist[nx][ny]=nd;pq.push({nd,nx,ny});parent[nx*n+ny].clear();parent[nx*n+ny].push_back(x*n+y);}elseif(nd==dist[nx][ny]){parent[nx*n+ny].push_back(x*n+y);}}}// 构建隐式图：从每个节点的前驱节点连边for(inti=0;i<n*n;i++)g[i].clear();for(inti=0;i<n;i++)for(intj=0;j<n;j++){if(i+j>=n)continue;for(autop:parent[i*n+j])g[p].push_back(i*n+j);}// 初始化记忆数组memset(dp,-1,sizeofdp);// 找出到达副对角线的最小总权重intbest=INF;for(inti=0;i<n;i++)best=min(best,dist[i][n-1-i]);// 设置副对角线上节点的 dp 值for(inti=0;i<n;i++)dp[i*n+n-1-i]=dist[i][n-1-i]==best;// 从起点 (0,0) 开始 DFS 统计最优路径数量cout<<dfs(0)<<"\n";}return0;}