做酒店网站设计网站设计师工作室

做酒店网站设计,网站设计师工作室,东莞线上推广平台,把网站做app题目描述 你有一个 nnn 行 nnn 列的网格#xff0c;每个单元格包含一个非零数字#xff08;111 到 999#xff09;。你需要从左上角 (0,0)(0,0)(0,0) 走到右下角 (n−1,n−1)(n-1,n-1)(n−1,n−1)#xff0c;每一步可以向上、下、左、右移动到相邻单元格#xff08;不能走…题目描述你有一个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个测试用例。每个测试用例以一个整数nnn2≤n≤1002 \le n \le 1002≤n≤100开始。接下来nnn行每行包含nnn个非零数字111-999。输入以n0n0n0结束。输出格式对每个测试用例输出最优对称路径的数量模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)的直线其上的点满足ijn−1i j n-1ijn−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)在副对角线上ijn−1ijn-1ijn−1则对称点就是它本身。因此整条路径关于副对角线对称我们可以只考虑副对角线及其左上方即ij≤n−1ij \le n-1ij≤n−1的区域另一半由对称性自动确定。路径权重的计算由于对称性当路径经过(i,j)(i,j)(i,j)和它的对称点时这两个单元格的数字都要计入总权重。但为了简化计算我们可以预先定义一个对称权重矩阵cost[i][j]cost[i][j]cost[i][j]表示如果路径经过(i,j)(i,j)(i,j)从而必然经过对称点应贡献的总数字和如果ijn−1ij n-1ijn−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]。注意我们只对ij≤n−1ij \le n-1ij≤n−1的区域定义costcostcost因为ijn−1ij n-1ijn−1的区域是对称的不需要重复计算。问题转化原问题转化为在只允许访问ij≤n−1ij \le n-1ij≤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)的对称路径必然经过副对角线上的某个点并且由于对称性路径在副对角线上的点“反射”后形成完整路径。因此我们只需要求出从(0,0)(0,0)(0,0)到每个副对角线点(k,n−1−k)(k, n-1-k)(k,n−1−k)的最小总权重。找出这些最小权重中的最小值minValueminValueminValue。统计所有从(0,0)(0,0)(0,0)到副对角线点且总权重等于minValueminValueminValue的路径数量。算法设计步骤1最短路径搜索这是一个带有非负权重的网格图最短路径问题可以使用Dijkstra\texttt{Dijkstra}Dijkstra算法。我们只考虑区域ij≤n−1ij \le n-1ij≤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×nji \times n ji×nj。对于每个节点vvv遍历其前驱节点列表parent[v]parent[v]parent[v]在图中添加一条有向边u→vu \to vu→vuuu是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}DFSdp[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//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN110;constintMOD1000000009,INF0x3f3f3f3f;constintdx[4]{1,-1,0,0},dy[4]{0,0,1,-1};intdist[MAXN][MAXN],grid[MAXN][MAXN],cost[MAXN][MAXN],dp[MAXN*MAXN];vectorintg[MAXN*MAXN];// 隐式图的邻接表vectorintparent[MAXN*MAXN];// 每个节点的最短路径前驱节点// 记忆化搜索从节点 u 出发到达副对角线的最优路径数量intdfs(intu){intanswer0;for(autov:g[u]){if(~dp[v])answer(answerdp[v])%MOD;elseanswer(answerdfs(v))%MOD;}returndp[u]answer;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn;while(cinnn){// 读入网格for(inti0;in;i)for(intj0;jn;j)cingrid[i][j];// 计算对称权重矩阵仅考虑副对角线及其左上方区域for(inti0;in;i)for(intj0;jn;j){if(ijn)continue;// 忽略右下方区域intsin-1-j,sjn-1-i;// 对称点坐标if(ijn-1)cost[i][j]grid[i][j];// 副对角线上的点elsecost[i][j]grid[i][j]grid[si][sj];// 非对角线点加上对称点权重}// Dijkstra 求最短路径memset(dist,0x3f,sizeofdist);for(inti0;in*n;i)parent[i].clear();dist[0][0]cost[0][0];usingstatetupleint,int,int;priority_queuestate,vectorstate,greaterstatepq;pq.push({dist[0][0],0,0});while(!pq.empty()){auto[d,x,y]pq.top();pq.pop();if(ddist[x][y])continue;for(intdir0;dir4;dir){intnxxdx[dir],nyydy[dir];// 确保在网格内且位于副对角线左上方if(nx0||nxn||ny0||nyn||nxnyn)continue;intnddcost[nx][ny];if(nddist[nx][ny]){dist[nx][ny]nd;pq.push({nd,nx,ny});parent[nx*nny].clear();parent[nx*nny].push_back(x*ny);}elseif(nddist[nx][ny]){parent[nx*nny].push_back(x*ny);}}}// 构建隐式图从每个节点的前驱节点连边for(inti0;in*n;i)g[i].clear();for(inti0;in;i)for(intj0;jn;j){if(ijn)continue;for(autop:parent[i*nj])g[p].push_back(i*nj);}// 初始化记忆数组memset(dp,-1,sizeofdp);// 找出到达副对角线的最小总权重intbestINF;for(inti0;in;i)bestmin(best,dist[i][n-1-i]);// 设置副对角线上节点的 dp 值for(inti0;in;i)dp[i*nn-1-i]dist[i][n-1-i]best;// 从起点 (0,0) 开始 DFS 统计最优路径数量coutdfs(0)\n;}return0;}