Editorial for Knights


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
#include <bits/stdc++.h>
using namespace std;

#define SZ 100
#define MX 2000

bool B[SZ][SZ];
int R[MX];
int C[MX];

bool dfs(int r, int c, int k)
{
    if(B[r][c])
        return false;
    vector<pair<int, int>> v;
    for(int dr = -2; dr <= 2; ++dr)
        for(int dc = -2; dc <= 2; ++dc)
            if(abs(dr) + abs(dc) == 3)
            {
                int rr = r + dr;
                int cc = c + dc;
                if(0 <= rr && rr < SZ && 0 <= cc && cc < SZ)
                    v.push_back(pair<int, int>(rr, cc));
            }
    int cnt = 0;
    for(auto a : v)
        if(B[a.first][a.second])
            ++cnt;
    if(cnt > 1)
        return false;
    R[k] = r;
    C[k] = c;
    B[r][c] = true;
    ++k;
    if(k == MX)
        return true;
    for(auto a : v)
        if(dfs(a.first, a.second, k))
            return true;
    B[r][c] = false;
    return false;
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    assert(dfs(0, 0, 0));
    vector<string> res(SZ, string(SZ, '#'));
    int pos = 0;
    for(int i = 0; i < n; ++i)
    {
        ++pos;
        for(int j = 0; j < a[i]; ++j)
        {
            res[R[pos]][C[pos]] = '.';
            ++pos;
        }
    }
    assert(pos <= MX);
    for(int i = 0; i < SZ; ++i)
        cout << res[i] << endl;
    return 0;
}