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.
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;
}