Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long int
- using namespace std;
- void mainSolve()
- {
- int n, m, k;
- cin >> n >> m >> k;
- vector<string> grid(n);
- for (int i = 0; i < n; i++)
- cin >> grid[i];
- vector<vector<vector<int> > > dp(n, vector<vector<int> >(m, vector<int>(2, 0)));
- dp[0][0][0] = k / 2 + (k % 2 == 1 && (grid[0][0] == '0'));
- dp[0][0][1] = k / 2 + (k % 2 == 1 && (grid[0][0] == '1'));
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < m; j++)
- {
- if ((i + j) == 0)
- continue;
- int total = 0;
- if (i > 0)
- total += dp[i - 1][j][1];
- if (j > 0)
- total += dp[i][j - 1][0];
- if (j == m - 1)
- {
- dp[i][j][0] = total;
- if (grid[i][j] == '1' && total > 0)
- {
- dp[i][j][1] = 1;
- dp[i][j][0] = total - 1;
- }
- }
- else if (i == n - 1)
- {
- dp[i][j][1] = total;
- if (grid[i][j] == '0' && total > 0)
- {
- dp[i][j][0] = 1;
- dp[i][j][1] = total - 1;
- }
- }
- else
- {
- dp[i][j][0] = dp[i][j][1] = total / 2;
- if (total % 2 == 1)
- {
- if (grid[i][j] == '1')
- ++dp[i][j][1];
- else
- ++dp[i][j][0];
- }
- }
- }
- }
- int x = 0, y = 0;
- while (true)
- {
- int total = dp[x][y][0] + dp[x][y][1];
- int grid_val = grid[x][y] - '0';
- if (total % 2 == 0)
- grid_val = 1 - grid_val;
- if (grid_val == 0)
- ++y;
- else
- ++x;
- total = dp[x][y][0] + dp[x][y][1];
- if (x == n - 1 && y == m - 1)
- break;
- if (x == n - 1 && (total > 1 || grid[x][y] == '1'))
- break;
- if (y == m - 1 && (total > 1 || grid[x][y] == '0'))
- break;
- }
- ++x;
- ++y;
- cout << x << " " << y << endl;
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int t;
- cin >> t;
- while (t--)
- {
- mainSolve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment