pratiyush7

Untitled

Mar 23rd, 2022
850
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.03 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. using namespace std;
  4.  
  5. void mainSolve()
  6. {
  7.   int n, m, k;
  8.   cin >> n >> m >> k;
  9.   vector<string> grid(n);
  10.   for (int i = 0; i < n; i++)
  11.     cin >> grid[i];
  12.   vector<vector<vector<int> > > dp(n, vector<vector<int> >(m, vector<int>(2, 0)));
  13.  
  14.   dp[0][0][0] = k / 2 + (k % 2 == 1 && (grid[0][0] == '0'));
  15.   dp[0][0][1] = k / 2 + (k % 2 == 1 && (grid[0][0] == '1'));
  16.  
  17.   for (int i = 0; i < n; i++)
  18.   {
  19.     for (int j = 0; j < m; j++)
  20.     {
  21.       if ((i + j) == 0)
  22.         continue;
  23.       int total = 0;
  24.       if (i > 0)
  25.         total += dp[i - 1][j][1];
  26.       if (j > 0)
  27.         total += dp[i][j - 1][0];
  28.  
  29.       if (j == m - 1)
  30.       {
  31.         dp[i][j][0] = total;
  32.         if (grid[i][j] == '1' && total > 0)
  33.         {
  34.           dp[i][j][1] = 1;
  35.           dp[i][j][0] = total - 1;
  36.         }
  37.       }
  38.       else if (i == n - 1)
  39.       {
  40.         dp[i][j][1] = total;
  41.         if (grid[i][j] == '0' && total > 0)
  42.         {
  43.           dp[i][j][0] = 1;
  44.           dp[i][j][1] = total - 1;
  45.         }
  46.       }
  47.       else
  48.       {
  49.         dp[i][j][0] = dp[i][j][1] = total / 2;
  50.         if (total % 2 == 1)
  51.         {
  52.           if (grid[i][j] == '1')
  53.             ++dp[i][j][1];
  54.           else
  55.             ++dp[i][j][0];
  56.         }
  57.       }
  58.     }
  59.   }
  60.  
  61.   int x = 0, y = 0;
  62.  
  63.   while (true)
  64.   {
  65.     int total = dp[x][y][0] + dp[x][y][1];
  66.     int grid_val = grid[x][y] - '0';
  67.     if (total % 2 == 0)
  68.       grid_val = 1 - grid_val;
  69.  
  70.     if (grid_val == 0)
  71.       ++y;
  72.     else
  73.       ++x;
  74.  
  75.     total = dp[x][y][0] + dp[x][y][1];
  76.  
  77.     if (x == n - 1 && y == m - 1)
  78.       break;
  79.     if (x == n - 1 && (total > 1 || grid[x][y] == '1'))
  80.       break;
  81.     if (y == m - 1 && (total > 1 || grid[x][y] == '0'))
  82.       break;
  83.   }
  84.  
  85.   ++x;
  86.   ++y;
  87.  
  88.   cout << x << " " << y << endl;
  89. }
  90.  
  91. int main()
  92. {
  93. #ifndef ONLINE_JUDGE
  94.   freopen("input.txt", "r", stdin);
  95.   freopen("output.txt", "w", stdout);
  96. #endif
  97.   int t;
  98.   cin >> t;
  99.   while (t--)
  100.   {
  101.     mainSolve();
  102.   }
  103.   return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment