SKAKAČ NAPADA - REŠENJE

Oblast: dvodimenzionalni nizovi - matrice

#include <iostream>
#include<string>
using namespace std;

int main()
{
  int m,n;
  cin>>m>>n;
  string tabla[9][9];
  for(int i=8; i>=1; i--)
{
  for(int j=1; j<=8; j++)
{
  if(i==m && j==n)
{
  int v=0;
  for(int r=i+2; r>=i-2; r--)
{

tabla[ i ][ j ]=" 0"; //Ispisuje 0 na mestu gde je zadata pozicija sa m i n
  if(r>i)
v++; //pomeranje kolone za polje koje napada skakač
  else if(r<i-1)
v--; //pomeranje kolone za polje koje napada skakač
  else if(r==i)   //U istom redu gde je skakač nema napadnutog polja, tu se stavlja zvezdica
{
tabla[i][j]=" *";
  continue;
}
  if(r<1||r>8)continue;    //van opsega

  int k1=n+v; //kolona napadnutog polja sa desne strane
  int k2=n-v;   //kolona napadnutog polja sa leve strane

  char kol1='a'+k1-1;    //oznaka kolone napadnutog polja desno(a-h)
  char kol2='a'+k2-1; //oznaka kolone napadnutog polja levo(a-h)
  char red='0'+r;   //oznaka redanapadnutog polja desno(1-8)
  string s1="";
s1+=kol1;
s1+=red;
  string s2="";
s2+=kol2;
s2+=red;

  if(k1<=8)
tabla[r][k1]=s1; //sifra napadnutog polja desno
  if(k2>=1)
tabla[r][k2]=s2;   //sifra napadnutog polja levo
}
}
  else
{
  if((tabla[i][j]).length()==0)
{
tabla[i][j]=" *"; //ostala polja popunjava sa zvezdicom
}

}
}
}
/* Ispisivanje*/
  for(int i=8; i>=1; i--)
{
  for(int j=1; j<=8; j++)
{

  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:

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č:

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.

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:

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:

for(int i=8; i>=1; i--)
{

for(int j=1; j<=8; j++)
{

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++.

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() {

int m, n;
cin >> m >> n;

string tabla[9][9];

// Definišemo sve moguće pomeraje skakača
int dx[] = {2, 2, 1, 1, -2, -2, -1, -1};
int dy[] = {1, -1, 2, -2, 1, -1, 2, -2};

for (int i = 8; i >= 1; --i) {

for (int j = 1; j <= 8; ++j) {

if (i == m && j == n) {

tabla[i][j] = " 0"; // Skakačeva pozicija

} else {

tabla[i][j] = " *"; // Pretpostavimo da je polje nenapadnuto

}

}

// Proveravamo sva polja koja skakač napada
for (int k = 0; k < 8; ++k) {

int ni = m + dx[k];
int nj = n + dy[k];
if (ni >= 1 && ni <= 8 && nj >= 1 && nj <= 8) {

char kol = 'a' + nj - 1;
char red = '0' + ni;
tabla[ni][nj] = string(1, kol) + red;

}

}

// Ispisivanje table
for (int i = 8; i >= 1; --i) {

for (int j = 1; j <= 8; ++j) {

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.