UVa 11617 An Odd Love

题目描述

春天到了，我们的朋友佩皮托（Pepito \texttt{Pepito}Pepito） 坠入了爱河。但他不确定她是否也爱他，于是他决定询问雏菊。他摘下一朵雏菊，交替说着“她爱我”和“她不爱我”，每说一句话就摘下一片花瓣。最后一片花瓣对应的那句话会告诉他他的爱是否得到了回应。

我们想帮助佩皮托总是得到“她爱我”的答案。因此，我们将通过摘掉花瓣数为偶数的雏菊上的一片花瓣，确保所有雏菊的花瓣数都是奇数。

我们有一片矩形的雏菊田，宽度为W WW，高度为H HH。田地的每个位置( w , h ) (w, h)(w,h)都有一朵雏菊，其中w = 1 , 2 , … , W w = 1, 2, \ldots, Ww=1,2,…,W，h = 1 , 2 , … , H h = 1, 2, \ldots, Hh=1,2,…,H。我们已经耐心地数了每朵雏菊的花瓣数P [ w , h ] P[w, h]P[w,h]。

从田地的左上角（即位置( 1 , 1 ) (1, 1)(1,1)）开始，你必须经过所有花瓣数为偶数的位置。如果你的当前位置是( w , h ) (w, h)(w,h)，你只能做三种移动：向下( h + 1 ) (h + 1)(h+1)、向左( w − 1 ) (w - 1)(w−1)和向右( w + 1 ) (w + 1)(w+1)。

你的任务是计算经过所有花瓣数为偶数的位置所需的最少移动次数。

输入格式

第一行包含一个整数，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数W WW和H HH，用空格分隔。接下来是H HH行，每行包含W WW个数字（1 11到9 99），表示对应雏菊的花瓣数。

输出格式

对于每个测试用例，输出一个整数，表示最少移动次数。

样例输入

5 5 3 54578 36329 75241 9 1 759456785 2 2 22 22 6 6 777777 772777 777777 777727 727777 777777 7 7 1811181 1118811 1881111 8111111 1188181 1881181 1111111

样例输出

11 7 3 11 24

题目分析

问题本质

这道题可以抽象为一个网格遍历问题：

1. 我们有一个H × W H \times WH×W的网格，每个格子有一个数字（1 11到9 99）。
2. 我们需要从左上角( 1 , 1 ) (1, 1)(1,1)出发。
3. 必须访问所有数字为偶数的格子（称为“目标点”）。
4. 移动方式只能向下、向左或向右，不能向上。
5. 需要计算最少移动步数。

关键约束

1. 不能向上移动：这意味着我们只能从上往下逐行遍历，一旦离开某一行就无法返回。
2. 必须访问所有偶数格子：这是我们的核心目标。
3. 起点固定：从( 1 , 1 ) (1, 1)(1,1)开始。

观察与简化

由于不能向上移动，我们的路径必然是单调向下的。这意味着：

1. 我们只能按行顺序访问：第1 11行 → 第2 22行 → … → 第H HH行。
2. 对于每一行，如果有偶数格子需要访问，我们必须在该行内水平移动来访问所有这些格子。
3. 对于没有偶数格子的行，我们只需从上一行的某个位置垂直向下移动一行，不需要水平移动。

进一步分析

对于一行中的多个偶数格子，访问它们的最优策略是：

1. 从该行的某个进入点开始。
2. 访问该行所有偶数格子。
3. 离开该行，准备进入下一行。

在一行内访问所有目标点的最小水平移动距离取决于：

• 进入点的列位置
• 该行最左目标点的列位置
• 该行最右目标点的列位置

实际上，对于一行有多个目标点的情况，访问所有点的最小水平移动方案只有两种：

1. 先到最左目标点，然后一路向右访问到最右目标点。
2. 先到最右目标点，然后一路向左访问到最左目标点。

状态设计

由于我们只关心有目标点的行（需要访问的行），可以忽略没有目标点的行，只需在行间转移时计算垂直移动距离。

定义状态：

• d p [ i ] [ 0 ] dp[i][0]dp[i][0]：访问完第i ii个目标行后，停在该行最左目标点的最小步数。
• d p [ i ] [ 1 ] dp[i][1]dp[i][1]：访问完第i ii个目标行后，停在该行最右目标点的最小步数。

状态转移

设第i − 1 i-1i−1个目标行在第r i − 1 r_{i-1}ri−1​行，最左目标点在l i − 1 l_{i-1}li−1​列，最右目标点在r i − 1 r_{i-1}ri−1​列。
设第i ii个目标行在第r i r_iri​行，最左目标点在l i l_ili​列，最右目标点在r i r_iri​列。
设两行之间的行距为g a p = r i − r i − 1 gap = r_i - r_{i-1}gap=ri​−ri−1​。

从d p [ i − 1 ] [ 0 ] dp[i-1][0]dp[i−1][0]（停在l i − 1 l_{i-1}li−1​）转移到d p [ i ] [ 0 ] dp[i][0]dp[i][0]（停在l i l_ili​）：

1. 方案 A：先到l i l_ili​，然后向右访问到r i r_iri​，再返回l i l_ili​。
   • 步数 =d p [ i − 1 ] [ 0 ] + g a p + ∣ l i − 1 − l i ∣ + ( r i − l i ) × 2 dp[i-1][0] + gap + |l_{i-1} - l_i| + (r_i - l_i) \times 2dp[i−1][0]+gap+∣li−1​−li​∣+(ri​−li​)×2
2. 方案 B：先到r i r_iri​，然后向左访问到l i l_ili​（自然停在l i l_ili​）。
   • 步数 =d p [ i − 1 ] [ 0 ] + g a p + ∣ l i − 1 − r i ∣ + ( r i − l i ) dp[i-1][0] + gap + |l_{i-1} - r_i| + (r_i - l_i)dp[i−1][0]+gap+∣li−1​−ri​∣+(ri​−li​)

从d p [ i − 1 ] [ 0 ] dp[i-1][0]dp[i−1][0]转移到d p [ i ] [ 1 ] dp[i][1]dp[i][1]（停在r i r_iri​）：

1. 方案 C：先到l i l_ili​，然后向右访问到r i r_iri​（自然停在r i r_iri​）。
   • 步数 =d p [ i − 1 ] [ 0 ] + g a p + ∣ l i − 1 − l i ∣ + ( r i − l i ) dp[i-1][0] + gap + |l_{i-1} - l_i| + (r_i - l_i)dp[i−1][0]+gap+∣li−1​−li​∣+(ri​−li​)
2. 方案 D：先到r i r_iri​，然后向左访问到l i l_ili​，再返回r i r_iri​。
   • 步数 =d p [ i − 1 ] [ 0 ] + g a p + ∣ l i − 1 − r i ∣ + ( r i − l i ) × 2 dp[i-1][0] + gap + |l_{i-1} - r_i| + (r_i - l_i) \times 2dp[i−1][0]+gap+∣li−1​−ri​∣+(ri​−li​)×2

从d p [ i − 1 ] [ 1 ] dp[i-1][1]dp[i−1][1]的转移类似，只需将l i − 1 l_{i-1}li−1​替换为r i − 1 r_{i-1}ri−1​。

初始化

对于第一个目标行（假设在第f i r s t R o w firstRowfirstRow行）：

• 从起点( 1 , 1 ) (1, 1)(1,1)出发，需要先垂直向下移动f i r s t R o w − 1 firstRow - 1firstRow−1行。
• 然后按照上述两种方案访问该行的所有目标点。

最终答案

访问完所有目标行后，答案为min ⁡ ( d p [ m − 1 ] [ 0 ] , d p [ m − 1 ] [ 1 ] ) \min(dp[m-1][0], dp[m-1][1])min(dp[m−1][0],dp[m−1][1])，其中m mm是目标行的数量。

如果整个网格没有目标点，答案为0 00。

算法步骤

1. 读取输入，找出所有有偶数格子的行及其列位置。
2. 如果没有目标行，输出0 00。
3. 初始化第一个目标行的d p dpdp值。
4. 对于每个后续目标行，计算从上一目标行转移过来的最小步数。
5. 输出最终的最小步数。

时间复杂度

• 预处理：O ( H × W ) O(H \times W)O(H×W)
• 动态规划：O ( m ) O(m)O(m)，其中m mm是目标行的数量（m ≤ H m \leq Hm≤H）
• 总时间复杂度：O ( H × W ) O(H \times W)O(H×W)，在题目限制下完全可行。

代码实现

// An Odd Love// UVa ID: 11617// Verdict: Accepted// Submission Date: 2025-12-15// UVa Run Time: 0.010s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){intt;cin>>t;while(t--){intW,H;cin>>W>>H;vector<string>grid(H);for(inti=0;i<H;i++)cin>>grid[i];// 存储有目标的行及其目标列vector<pair<int,vector<int>>>targetRows;for(inth=0;h<H;h++){vector<int>cols;for(intw=0;w<W;w++){if((grid[h][w]-'0')%2==0)cols.push_back(w);}if(!cols.empty()){targetRows.push_back({h,cols});}}// 如果没有目标行，答案就是0（从起点开始不用移动）if(targetRows.empty()){cout<<0<<endl;continue;}constintINF=1e9;intm=targetRows.size();vector<vector<int>>dp(m,vector<int>(2,INF));// 初始化第一个目标行intfirstRow=targetRows[0].first;vector<int>firstCols=targetRows[0].second;intfirstLeft=*min_element(firstCols.begin(),firstCols.end());intfirstRight=*max_element(firstCols.begin(),firstCols.end());intfirstRowDist=firstRight-firstLeft;// 从起点(0,0)到第一个目标行// 需要先向下移动firstRow行intdownSteps=firstRow;// 从第0行到第firstRow行// 停在左端点dp[0][0]=downSteps+firstLeft+firstRowDist+firstRowDist;// 下移，到最左，到最右，回最左dp[0][0]=min(dp[0][0],downSteps+firstRight+firstRowDist);// 下移，到最右，到最左// 停在右端点dp[0][1]=downSteps+firstLeft+firstRowDist;// 下移，到最左，到最右dp[0][1]=min(dp[0][1],downSteps+firstRight+firstRowDist+firstRowDist);// 下移，到最右，到最左，回最右// 处理后续目标行for(inti=1;i<m;i++){intprevRow=targetRows[i-1].first;vector<int>prevCols=targetRows[i-1].second;intprevLeft=*min_element(prevCols.begin(),prevCols.end());intprevRight=*max_element(prevCols.begin(),prevCols.end());intcurrRow=targetRows[i].first;vector<int>currCols=targetRows[i].second;intcurrLeft=*min_element(currCols.begin(),currCols.end());intcurrRight=*max_element(currCols.begin(),currCols.end());intcurrRowDist=currRight-currLeft;introwGap=currRow-prevRow;// 行间距离for(intprevSide=0;prevSide<2;prevSide++){if(dp[i-1][prevSide]==INF)continue;intprevCol=(prevSide==0)?prevLeft:prevRight;// 从上一目标行到当前目标行// 中间需要下移rowGap行// 我们可以选择在中间行的任意列移动// 对于停在左端点// 方案1：先到当前行最左，访问到最右，然后回到最左intcost1=dp[i-1][prevSide]+rowGap+abs(prevCol-currLeft)+currRowDist+currRowDist;// 方案2：先到当前行最右，访问到最左（停在最左）intcost2=dp[i-1][prevSide]+rowGap+abs(prevCol-currRight)+currRowDist;dp[i][0]=min(dp[i][0],min(cost1,cost2));// 对于停在右端点// 方案3：先到当前行最左，访问到最右（停在最右）intcost3=dp[i-1][prevSide]+rowGap+abs(prevCol-currLeft)+currRowDist;// 方案4：先到当前行最右，访问到最左，然后回到最右intcost4=dp[i-1][prevSide]+rowGap+abs(prevCol-currRight)+currRowDist+currRowDist;dp[i][1]=min(dp[i][1],min(cost3,cost4));}}intans=min(dp[m-1][0],dp[m-1][1]);cout<<ans<<endl;}return0;}