U donjem levom ćošku šahovske table dimenzija \(n \times n\) se nalazi skakač. On se kreće tako što izabere jedan od 4 smera (gore, dole, levo i desno), pomeri se 2 polja u tom smeru, a zatim odabere jedan od smerova koji su normalni u odnosu na prvi smer kretanja i pomeri se još jedno polje u tom smeru (nalik slovu L).
Neka od polja na tabli su zauzeta figurama. Ispitati sva polja koja skakač može da obiđe, bez da stane na zauzeto polje.
Sa standardnog ulaza se učitava broj \(n\) (\(3 \leq n \leq 10\)), a zatim i matrica dimenzija \(n \times n\) čiji elementi imaju vrednosti 0 ili 1. Ukoliko element ima vrednost 1, označava zauzeto polje, a ukoliko ima vrednost 0, označava slobodno polje. Računati da je element u donjem levom ćošku uvek 1 (jer skakač stoji na tom polju na početku).
Ipisati izmenjenu matricu table tako da slobodna polja do kojih skakač može da dođe sadrže vrednost 2.
4 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 0
0 1 1 2 2 1 1 1 0 1 2 2 1 2 1 0
U ovom bloku se opisuje glavno rešenje zadatka.
#include <iostream>
#include <vector>
using namespace std;
static const vector<pair<int, int>> moves = {
{1, 2}, {1, -2}, {-1, 2}, {-1, -2},
{2, 1}, {2, -1}, {-2, 1}, {-2, -1}
};
void knight_tour(vector<vector<int>> &B, int row, int col)
{
const int n = B.size();
for (auto move : moves) {
int new_row = row + move.first;
int new_col = col + move.second;
if (new_row < 0 || new_row >= n ||
new_col < 0 || new_col >= n) {
continue;
}
if (B[new_row][new_col] != 0) {
continue;
}
B[new_row][new_col] = 2;
knight_tour(B, new_row, new_col);
}
}
int main()
{
int n; cin >> n;
vector<vector<int>> B(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> B[i][j];
}
}
knight_tour(B, n - 1, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << B[i][j] << " ";
}
cout << endl;
}
return 0;
}