You are viewing a single comment's thread. Return to all comments →
recursion on the length of path, O(n*m*k)
int coinOnTheTable(int n, int m, int K, int P1, int P2, const vector<vector<char>>& board) { vector<vector<vector<int>>> cache(n + 2, vector<vector<int>>(m + 2, vector<int>(K + 1, 10000))); cache[1][1][0] = 0; for (int t = 1; t <= K; t++) { cache[1][1][t] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (i == 1 and j == 1) continue; int left = (board[i][j - 1] == 'R') ? cache[i][j - 1][t - 1] : cache[i][j - 1][t - 1] + 1; int right = (board[i][j + 1] == 'L') ? cache[i][j + 1][t - 1] : cache[i][j + 1][t - 1] + 1; int up = (board[i - 1][j] == 'D') ? cache[i - 1][j][t - 1] : cache[i - 1][j][t - 1] + 1; int down = (board[i + 1][j] == 'U') ? cache[i + 1][j][t - 1] : cache[i + 1][j][t - 1] + 1; cache[i][j][t] = min({ left, right, up, down }); } } } return (cache[P1][P2][K] <= 2601) ? cache[P1][P2][K] : -1; } int main() { int n, m, K, P1, P2; string s; cin >> n >> m >> K; vector<vector<char>> board(n + 2, vector<char>(m + 2)); for (int i = 1; i <= n; i++) { cin >> s; for (int j=1; j <= s.size(); j++) { board[i][j] = s[j - 1]; if (s[j-1] == '*') { P1 = i; P2 = j; } } } cout << coinOnTheTable(n, m, K, P1, P2, board); }
Seems like cookies are disabled on this browser, please enable them to open this website
Coin on the Table
You are viewing a single comment's thread. Return to all comments →
recursion on the length of path, O(n*m*k)