ICPC Contest-week1-A

#include <bits/stdc++.h>
using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
#define NeedForSpeed                  \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define int long long
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vpi;
#define f first
#define s second
#define endl "\n"
const int mod = 1000000007;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
vector<vector<char>> grid;
string invalid;
int n;
int matchlen;
// 8 possible moves (all unique)
int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};
int totalcnt = 0;
map<char, pair<int, int>> mp;
void dfs(char key, int idx, int cnt)
{
    if (idx == matchlen)
    {
        return;
    }
    if (cnt == n)
    {
        totalcnt++;
        return;
    }
    int r = mp[key].f;
    int c = mp[key].s;
    for (int i = 0; i < 8; i++)
    {
        int nr = r + dx[i];
        int nc = c + dy[i];
        // validity check
        if (nr >= 0 && nr < 4 && nc >= 0 && nc < 3 && grid[nr][nc] != '.' && grid[nr][nc] != invalid[idx])
        {
            dfs(grid[nr][nc], 0, cnt + 1);
        }
        else if (nr >= 0 && nr < 4 && nc >= 0 && nc < 3 && grid[nr][nc] != '.' && grid[nr][nc] == invalid[idx])
        {
            dfs(grid[nr][nc], idx + 1, cnt + 1);
        }
    }
    return;
}
signed main()
{
    NeedForSpeed;
    int m, k;
    cin >> n >> m >> k;
    // grid constructed
    grid.push_back({'1', '2', '3'});
    grid.push_back({'4', '5', '6'});
    grid.push_back({'7', '8', '9'});
    grid.push_back({'.', '0', '.'});
    // hash the grid, row-column of the grid
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            if (grid[i][j] != '.')
            {
                mp[grid[i][j]] = {i, j};
            }
        }
    }
    invalid = to_string(m);
    matchlen = invalid.length();
    char key = static_cast<char>(k);
    int idx = 0;
    dfs(key, idx, 0);
    cout << totalcnt << endl;
    return 0;
}