SKAKAČ NAPADA - REŠENJE
Oblast: dvodimenzionalni nizovi - matrice
#include <iostream>
#include <string>
using namespace std;
int main() {
#include <string>
using namespace std;
int main() {
// Unos koordinata pozicije skakača (red i kolona)
int m, n;
cin >> m >> n;
// Inicijalizacija table kao matrice stringova
string tabla[9][9];
// Popunjavanje table od reda 8 ka 1
for (int i = 8; i >= 1; i--) {
// Ispisivanje sadržaja table
for (int i = 8; i >= 1; i--) {
return 0;
}
int m, n;
cin >> m >> n;
// Inicijalizacija table kao matrice stringova
string tabla[9][9];
// Popunjavanje table od reda 8 ka 1
for (int i = 8; i >= 1; i--) {
for (int j = 1; j <= 8; j++) {
}
if (i == m && j == n) { // Ako je trenutna pozicija skakač
}
int v = 0; // Pomoćna promenljiva za pomeranje kolona
for (int r = i + 2; r >= i - 2; r--) {
} else {for (int r = i + 2; r >= i - 2; r--) {
// Postavljanje '0' na poziciju skakača
tabla[i][j] = " 0";
if (r > i) v++; // Pomeranje kolone nadesno
else if (r < i - 1) v--; // Pomeranje kolone nalevo
else if (r == i) {
// Ignorisanje pozicija van granica table
if (r < 1 || r > 8) continue;
// Izračunavanje kolona za desno i levo napadnuto polje
int k1 = n + v; // Desno
int k2 = n - v; // Levo
// Generisanje oznaka polja (npr. 'c4')
char kol1 = 'a' + k1 - 1;
char kol2 = 'a' + k2 - 1;
char red = '0' + r;
string s1 = ""; // Napadnuto polje desno
s1 += kol1;
s1 += red;
string s2 = ""; // Napadnuto polje levo
s2 += kol2;
s2 += red;
// Postavljanje napadnutih polja na tablu
if (k1 <= 8) tabla[r][k1] = s1;
if (k2 >= 1) tabla[r][k2] = s2;
}tabla[i][j] = " 0";
if (r > i) v++; // Pomeranje kolone nadesno
else if (r < i - 1) v--; // Pomeranje kolone nalevo
else if (r == i) {
// U istom redu kao skakač se postavlja '*'
tabla[i][j] = " *";
continue;
}tabla[i][j] = " *";
continue;
// Ignorisanje pozicija van granica table
if (r < 1 || r > 8) continue;
// Izračunavanje kolona za desno i levo napadnuto polje
int k1 = n + v; // Desno
int k2 = n - v; // Levo
// Generisanje oznaka polja (npr. 'c4')
char kol1 = 'a' + k1 - 1;
char kol2 = 'a' + k2 - 1;
char red = '0' + r;
string s1 = ""; // Napadnuto polje desno
s1 += kol1;
s1 += red;
string s2 = ""; // Napadnuto polje levo
s2 += kol2;
s2 += red;
// Postavljanje napadnutih polja na tablu
if (k1 <= 8) tabla[r][k1] = s1;
if (k2 >= 1) tabla[r][k2] = s2;
if (tabla[i][j].length() == 0) {
}
// Popunjavanje ostalih polja sa '*'
tabla[i][j] = " *";
}tabla[i][j] = " *";
// Ispisivanje sadržaja table
for (int i = 8; i >= 1; i--) {
for (int j = 1; j <= 8; j++) {
cout << endl;
}
cout << tabla[i][j] << " ";
}cout << endl;
return 0;
Ključni delovi koda i objašnjenje
Inicijalizacija table:
string tabla[9][9];
Kreira se dvodimenzionalni niz stringova dimenzija 9x9, koji će predstavljati šahovsku tablu. Iako tabla ima dimenzije 8x8, koristi se matrica 9x9 zbog lakšeg indeksiranja (indeksi idu od 1 do 8, što odgovara šahovskoj notaciji).
Petlja za popunjavanje table:
for(int i=8; i>=1; i--)
{
{
for(int j=1; j<=8; j++)
{
{
Ova petlja prolazi kroz sve pozicije na šahovskoj tabli, počevši od donjeg reda (i=8) ka vrhu (i=1), i od leve ka desnoj koloni (j=1 do j=8).
Identifikacija pozicije skakača:
Identifikacija pozicije skakača:
if(i==m && j==n)
Kada se dođe do pozicije skakača (m, n), program započinje proces označavanja polja koja skakač napada.
Označavanje polja koja napada skakač:
Označavanje polja koja napada skakač:
for(int r=i+2; r>=i-2; r--)
Ova petlja iterira kroz sve moguće redove koje skakač može napasti (dva reda iznad i dva ispod pozicije skakača). Promena varijable v služi za označavanje pomaka kolona u zavisnosti od trenutnog reda.
Označavanje pozicije skakača:
- k1 i k2 su kolone koje skakač napada.
- kol1 i kol2 su oznake tih kolona (a-h).
- red predstavlja red koji skakač napada (1-8).
- s1 i s2 su šifre polja koja skakač napada.
Označavanje pozicije skakača:
tabla[i][j]=" 0";
Na poziciji gde se nalazi skakač postavlja se " 0" kako bi se označilo da je to skakačeva pozicija.
Popunjavanje ostalih polja:
Popunjavanje ostalih polja:
if((tabla[i][j]).length()==0)
{
{
tabla[i][j]=" *";
}Sva ostala polja koja nisu napadnuta ili na kojima se ne nalazi skakač popunjavaju se zvezdicama (*).
Ispisivanje table:
Ispisivanje table:
for(int i=8; i>=1; i--)
{
{
for(int j=1; j<=8; j++)
{
cout << endl;
}{
cout << tabla[i][j] << " ";
}cout << endl;
Na kraju se tabla ispisuje tako da svaka linija predstavlja jedan red na šahovskoj tabli.
RezultatKao rezultat, na izlazu se dobija šahovska tabla sa oznakama polja koje skakač napada, pozicijom skakača označenom sa " 0", i ostalim poljima ispunjenim zvezdicama.
Ovaj program lepo prikazuje osnovne principe rada sa dvodimenzionalnim nizovima, manipulacije stringovima, i osnovne koncepte algoritama u C++.
RezultatKao rezultat, na izlazu se dobija šahovska tabla sa oznakama polja koje skakač napada, pozicijom skakača označenom sa " 0", i ostalim poljima ispunjenim zvezdicama.
Ovaj program lepo prikazuje osnovne principe rada sa dvodimenzionalnim nizovima, manipulacije stringovima, i osnovne koncepte algoritama u C++.
Analiza optimalnosti koda
- Višak iteracija:
- Trenutni kod koristi petlju koja prolazi kroz 25 mogućih pozicija oko skakača, što uključuje i one koje skakač ne može dosegnuti. Skakač može napasti samo osam specifičnih pozicija (ukoliko su unutar granica table), pa je pregledavanje svih ovih 25 pozicija nepotrebno.
- Redundantno postavljanje zvezdica:
- Kod prvo prolazi kroz sve pozicije i postavlja zvezdicu (*) na svaku koja nije napadnuta. Ovaj proces bi mogao da se optimizuje tako da se zvezdice postavljaju tokom prvog prolaska kroz matricu, a ne nakon provere svih polja.
Optimizovan kod
#include <iostream>
#include <string>
using namespace std;
int main() {
#include <string>
using namespace std;
int main() {
// Unos pozicije skakača (red i kolona)
int m, n;
cin >> m >> n;
// Matrica za predstavljanje šahovske table
string tabla[9][9];
// Definisanje svih mogućih skakačevih pomeraja
int dx[] = {2, 2, 1, 1, -2, -2, -1, -1};
int dy[] = {1, -1, 2, -2, 1, -1, 2, -2};
// Popunjavanje table sa početnim vrednostima
for (int i = 8; i >= 1; --i) {
// Proveravanje polja koja skakač može napasti
for (int k = 0; k < 8; ++k) {
// Ispisivanje šahovske table
for (int i = 8; i >= 1; --i) {
return 0;
}
int m, n;
cin >> m >> n;
// Matrica za predstavljanje šahovske table
string tabla[9][9];
// Definisanje svih mogućih skakačevih pomeraja
int dx[] = {2, 2, 1, 1, -2, -2, -1, -1};
int dy[] = {1, -1, 2, -2, 1, -1, 2, -2};
// Popunjavanje table sa početnim vrednostima
for (int i = 8; i >= 1; --i) {
for (int j = 1; j <= 8; ++j) {
}
if (i == m && j == n) {
}
// Skakačeva trenutna pozicija označena sa "0"
tabla[i][j] = " 0";
} else {tabla[i][j] = " 0";
// Sva ostala polja pretpostavljamo kao nenapadnuta
tabla[i][j] = " *";
}tabla[i][j] = " *";
// Proveravanje polja koja skakač može napasti
for (int k = 0; k < 8; ++k) {
// Nove koordinate skakačevog poteza
int ni = m + dx[k];
int nj = n + dy[k];
if (ni >= 1 && ni <= 8 && nj >= 1 && nj <= 8) {
}int ni = m + dx[k];
int nj = n + dy[k];
if (ni >= 1 && ni <= 8 && nj >= 1 && nj <= 8) {
// Pretvaranje koordinata u šahovski format (npr. c4)
char kol = 'a' + nj - 1;
char red = '0' + ni;
tabla[ni][nj] = string(1, kol) + red;
}char kol = 'a' + nj - 1;
char red = '0' + ni;
tabla[ni][nj] = string(1, kol) + red;
// Ispisivanje šahovske table
for (int i = 8; i >= 1; --i) {
for (int j = 1; j <= 8; ++j) {
cout << endl;
}
cout << tabla[i][j] << " ";
}cout << endl;
return 0;
Poboljšanja u Optimizovanom Kodu
- Jasnoća i jednostavnost: Svi mogući pomeraji skakača su jasno definisani u dva niza (dx i dy). Ovi nizovi omogućavaju jednostavno iteriranje kroz sve moguće pozicije koje skakač može napasti.
- Efikasnost: Kod sada koristi samo jednu petlju za iteriranje kroz sve napadnute pozicije, umesto nepotrebnih iteracija kroz pozicije koje skakač ne može napasti.
- Tačnost: Ovaj kod takođe proverava da li su napadnuta polja unutar granica table, čime se izbegava postavljanje šifri na nepostojeća polja.