C ++程序找出操作数以最大化网格中偶数单元格的数量

• Z时代
• 2024-01-10
• 分类：综合

假设，我们有一个尺寸为 h * w 的网格。网格中的每个单元格都有一个特定的值分配给它。我们必须最大化具有偶数值的单元格。为此，我们可以选择一个之前没有被选中的单元格，然后将当前单元格的值减 1，并将与当前单元格垂直或水平相邻的另一个单元格的值加 1。我们打印出操作数和增加和减少操作的单元格数。输出将采用以下格式 -

• 操作次数

• 1st（减少单元格位置）-（增加单元格位置）

  ……

• nth（减少的单元格位置）-（增加的单元格位置）

所以，如果输入像 h = 3, w = 3, grid = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}}，那么输出将是

4
(0, 1) - (0, 2)
(2, 0) - (2, 1)
(2, 1) - (2, 2)
(0, 2) - (1, 2)

脚步

为了解决这个问题，我们将遵循以下步骤 -

Define a new array result that contains a tuple
for initialize i := 0, when i < h, update (increase i by 1), do:
   tp := 0
   for initialize j := 0, when j < w, update (increase j by 1), do:
      if tp > 0, then:
         insert tuple(i, j - 1, i, j) at the end of result
         grid[i, j] := grid[i, j] + tp
      if grid[i, j] mod 2 is same as 1 and j < w-1, then:
         grid[i, j] := grid[i, j] - 1
         tp := 1
      Otherwise
         tp := 0
tp := 0
for initialize i := 0, when i < h, update (increase i by 1), do:
   if tp > 0, then:
  insert tuple(i - 1, w - 1, i, w - 1) at the end of result
grid[i, w - 1] := grid[i, w - 1] + tp
if grid[i, w - 1] mod 2 is same as 1, then:
grid[i, w - 1] := grid[i, w - 1] - 1
tp := 1
Otherwise
tp := 0
print(size of result)
for initialize i := 0, when i < size of result, update (increase i by 1), do:
print('(' + first value of result[i] + ',' + second value of result[i] + '- (' + third value of result[i] + ',' + fourth value of result[i])

示例

让我们看看以下实现以更好地理解 -

#include <bits/stdc++.h>
using namespace std;
void solve(int h, int w, vector<vector<int>>grid){
   vector<tuple<int,int,int,int>> result;
   for(int i = 0; i < h; i++){
      int tp = 0;
      for(int j = 0; j < w; j++){
         if(tp > 0){
            result.push_back(make_tuple(i, j-1, i, j));
            grid[i][j] += tp;
         }
         if(grid[i][j]%2 == 1 && j < w-1){
            grid[i][j] -= 1;
            tp = 1;
         }
         else
            tp = 0;
      }
   }
   int tp = 0;
   for(int i = 0; i < h; i++){
      if(tp > 0){
         result.push_back(make_tuple(i-1, w-1, i, w-1));
         grid[i][w-1] += tp;
      }
      if(grid[i][w-1]%2 == 1){
         grid[i][w-1] -= 1;
         tp = 1;
      }
      else
         tp = 0;
   }
   cout << (int)result.size() << endl;
   for(int i = 0; i < (int)result.size(); i++){
      cout << "(" << get<0>(result[i]) << ", " << get<1>(result[i])
      << ")" << " - (" << get<2>(result[i]) << ", " << get<3>(result[i]) << ")";
      cout << '\n';
   }
}
int main() {
   int h = 3, w = 3 ;
   vector<vector<int>> grid = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}};
   solve(h, w, grid);
   return 0;
}

输入

3, 3, {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}}

4
(0, 1) - (0, 2)
(2, 0) - (2, 1)
(2, 1) - (2, 2)
(0, 2) - (1, 2)

以上是 C ++程序找出操作数以最大化网格中偶数单元格的数量 的全部内容， 来源链接： utcz.com/z/297226.html