USACO 2021 December Contest Bronze Division - Walking Home

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

For those of you familiar with gold level techniques, this problem can easily be done with DP, however that's not the point of the bronze division.

The dp idea would be smth like dp[i][j][dir][chg] - # of ways to get to (i, j) if dir is 0/1 and we changed chg times

However, the constraints are small so we will do some brute force/complete search to count the answer which is implemented easily using recursion.

Source codes

The source code in C++ can be seen below (the described method times out in Python, however there are other approaches as well, including casework ones, which work in Python).

#include <bits/stdc++.h>
using namespace std;

int n, k, ans = 0;
char grid[52][52];

void bkt(int L, int C, int dir, int chg)
{
    if(chg > k)
        return;
    if(L == n-1 && C == n-1)
    {
        ans++;
        return;
    }
    if(C+1 < n && grid[L][C+1] == '.')
        bkt(L, C+1, 0, chg + (dir == 1));
    if(L+1 < n && grid[L+1][C] == '.')
        bkt(L+1, C, 1, chg + (dir == 0));
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    for(; t; t--)
    {
        cin >> n >> k;
        ans = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                cin >> grid[i][j];
        if(grid[0][1] != 'H')
            bkt(0, 1, 0, 0);
        if(grid[1][0] != 'H')
            bkt(1, 0, 1, 0);
        cout << ans << '\n';
    }
    return 0;
}