• + 0 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);
    }