fork download 
  1. /*
  2.     Problem: Minimum Flip Cost to Create a Same-Color Grid Path
  3.     Company Tag: Infosys
  4.  
  5.     Problem Statement:
  6.         We are given an N x M binary grid.
  7.  
  8.         We can flip:
  9.             - any row i with cost R[i]
  10.             - any column j with cost C[j]
  11.  
  12.         Flipping changes 0 to 1 and 1 to 0.
  13.  
  14.         We need a path from top-left to bottom-right such that:
  15.             - we only move right or down
  16.             - all cells on the path have the same color
  17.  
  18.         Return the minimum total flip cost.
  19.  
  20.     Constraints:
  21.         2 <= N <= 1000
  22.         2 <= M <= 1000
  23.         1 <= R[i] <= 100
  24.         1 <= C[j] <= 100
  25.         grid[i][j] is either '0' or '1'
  26.         A valid solution is always possible.
  27.  
  28.     Simple Brute Force:
  29.         Try every possible set of flipped rows and columns.
  30.  
  31.     Why Brute Force Fails:
  32.         There are 2^N row choices and 2^M column choices.
  33.  
  34.     Better Idea:
  35.         Use dynamic programming on the path.
  36.  
  37.         Final color of cell (i, j) is:
  38.  
  39.             grid[i][j] XOR rowFlip[i] XOR colFlip[j]
  40.  
  41.         We try both target colors:
  42.             target = 0
  43.             target = 1
  44.  
  45.         DP state:
  46.             dp[i][j][rowFlip][colFlip]
  47.  
  48.         Meaning:
  49.             minimum cost to reach cell (i, j)
  50.             when current row has rowFlip state
  51.             and current column has colFlip state.
  52.  
  53.     Dry Run:
  54.         Grid:
  55.             0 1
  56.             1 1
  57.  
  58.         Row costs:
  59.             3, 4
  60.  
  61.         Column costs:
  62.             5, 2
  63.  
  64.         Flip column 2.
  65.  
  66.         Grid becomes:
  67.             0 0
  68.             1 0
  69.  
  70.         Path:
  71.             (1,1) -> (1,2) -> (2,2)
  72.  
  73.         Total cost = 2
  74.  
  75.     Time Complexity:
  76.         O(N * M)
  77.  
  78.     Space Complexity:
  79.         O(N * M)
  80. */
  81.  
  82. #include <bits/stdc++.h>
  83. using namespace std;
  84.  
  85. long long minimumFlipCost(
  86.     int N,
  87.     int M,
  88.     vector<int>& rowCost,
  89.     vector<int>& colCost,
  90.     vector<string>& grid
  91. ) {
  92.     const long long INF = (1LL << 60);
  93.  
  94.     long long answer = INF;
  95.  
  96.     for (int targetColor = 0; targetColor <= 1; targetColor++) {
  97.         /*
  98.             Each cell has 4 states:
  99.                 state 0 -> rowFlip = 0, colFlip = 0
  100.                 state 1 -> rowFlip = 0, colFlip = 1
  101.                 state 2 -> rowFlip = 1, colFlip = 0
  102.                 state 3 -> rowFlip = 1, colFlip = 1
  103.         */
  104.         vector<vector<array<long long, 4>>> dp(
  105.             N,
  106.             vector<array<long long, 4>>(M)
  107.         );
  108.  
  109.         for (int i = 0; i < N; i++) {
  110.             for (int j = 0; j < M; j++) {
  111.                 for (int state = 0; state < 4; state++) {
  112.                     dp[i][j][state] = INF;
  113.                 }
  114.             }
  115.         }
  116.  
  117.         for (int rowFlip = 0; rowFlip <= 1; rowFlip++) {
  118.             for (int colFlip = 0; colFlip <= 1; colFlip++) {
  119.                 int finalColor = (grid[0][0] - '0') ^ rowFlip ^ colFlip;
  120.  
  121.                 if (finalColor == targetColor) {
  122.                     long long cost = 0;
  123.  
  124.                     if (rowFlip) {
  125.                         cost += rowCost[0];
  126.                     }
  127.  
  128.                     if (colFlip) {
  129.                         cost += colCost[0];
  130.                     }
  131.  
  132.                     int state = rowFlip * 2 + colFlip;
  133.                     dp[0][0][state] = cost;
  134.                 }
  135.             }
  136.         }
  137.  
  138.         for (int i = 0; i < N; i++) {
  139.             for (int j = 0; j < M; j++) {
  140.                 for (int state = 0; state < 4; state++) {
  141.                     long long currentCost = dp[i][j][state];
  142.  
  143.                     if (currentCost >= INF) {
  144.                         continue;
  145.                     }
  146.  
  147.                     int rowFlip = state / 2;
  148.                     int colFlip = state % 2;
  149.  
  150.                     // Move right. Row flip stays the same, new column flip can be chosen.
  151.                     if (j + 1 < M) {
  152.                         for (int nextColFlip = 0; nextColFlip <= 1; nextColFlip++) {
  153.                             int finalColor =
  154.                                 (grid[i][j + 1] - '0') ^ rowFlip ^ nextColFlip;
  155.  
  156.                             if (finalColor == targetColor) {
  157.                                 long long newCost = currentCost;
  158.  
  159.                                 if (nextColFlip) {
  160.                                     newCost += colCost[j + 1];
  161.                                 }
  162.  
  163.                                 int nextState = rowFlip * 2 + nextColFlip;
  164.  
  165.                                 dp[i][j + 1][nextState] =
  166.                                     min(dp[i][j + 1][nextState], newCost);
  167.                             }
  168.                         }
  169.                     }
  170.  
  171.                     // Move down. Column flip stays the same, new row flip can be chosen.
  172.                     if (i + 1 < N) {
  173.                         for (int nextRowFlip = 0; nextRowFlip <= 1; nextRowFlip++) {
  174.                             int finalColor =
  175.                                 (grid[i + 1][j] - '0') ^ nextRowFlip ^ colFlip;
  176.  
  177.                             if (finalColor == targetColor) {
  178.                                 long long newCost = currentCost;
  179.  
  180.                                 if (nextRowFlip) {
  181.                                     newCost += rowCost[i + 1];
  182.                                 }
  183.  
  184.                                 int nextState = nextRowFlip * 2 + colFlip;
  185.  
  186.                                 dp[i + 1][j][nextState] =
  187.                                     min(dp[i + 1][j][nextState], newCost);
  188.                             }
  189.                         }
  190.                     }
  191.                 }
  192.             }
  193.         }
  194.  
  195.         for (int state = 0; state < 4; state++) {
  196.             answer = min(answer, dp[N - 1][M - 1][state]);
  197.         }
  198.     }
  199.  
  200.     return answer;
  201. }
  202.  
  203. int main() {
  204.     int N, M;
  205.     cin >> N >> M;
  206.  
  207.     vector<int> rowCost(N);
  208.     vector<int> colCost(M);
  209.  
  210.     for (int i = 0; i < N; i++) {
  211.         cin >> rowCost[i];
  212.     }
  213.  
  214.     for (int j = 0; j < M; j++) {
  215.         cin >> colCost[j];
  216.     }
  217.  
  218.     vector<string> grid(N);
  219.  
  220.     for (int i = 0; i < N; i++) {
  221.         cin >> grid[i];
  222.     }
  223.  
  224.     cout << minimumFlipCost(N, M, rowCost, colCost, grid) << endl;
  225.  
  226.     return 0;
  227. }
Runtime error #stdin #stdout 1.05s 2096040KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Iy5jBw
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!