Se consideră o tablă de şah cu n linii şi m coloane. La o poziţie dată se află un cal de şah, acesta putându-se deplasa pe tablă în modul specific acestei piese de şah (în L).
Să se determine o modalitate de parcurgere a tablei de către calul dat, astfel încât acesta să nu treacă de două ori prin aceeaşi poziţie. Parcurgerea constă într-o matrice cu n linii și m coloane, fiecare element al matricei având valoarea pasului la care se ajunge în acel element, sau 0, dacă nu s-a ajuns.
Date de intrare
Fișierul de intrare saritura_calului1.in conține numerele n şi m , apoi numere x y, reprezentând dimensiunile tablei (numărul de linii şi numărul de coloane) , respectiv coordonatele iniţiale ale calului (linie, coloana).
Date de ieşire
Fișierul de ieșire saritura_calului1.out va conține n linii cu câte m numere naturale cuprinse între 1 și n*m, separate prin exact un spațiu, reprezentând parcurgerea solicitată.
Restricţii şi precizări
1 ≤ n,m ≤ 100
1 ≤ istart ≤ n
1 ≤ jstart ≤ m
scorul obținut pe fiecare test este proporțional cu gradul de acoperire a tablei. Astfel, dacă tabla este acoperită în întregime, se acordă 100% din punctaj. Dacă tabla este acoperită în proporție de 70%, se acordă 70% din punctaj, etc.
Exemplul 1
saritura_calului1.in
4 5 1 1
saritura_calului1.out
1 12 7 16 3
6 17 2 11 8
13 10 19 4 15
18 5 14 9 20
pbinfo 284.
am incercat sa fac un greedy dar iau maxim 39.dupa am incercat backtracking si am luat 40 cu limite de timp
Backtracking: https://pastebin.com/hbPvddX4 40 de puncte.
Greedy: https://pastebin.com/HVrKSzD1 39 de puncte.
nu vreau solutia/sursa de 100 .vreau doar o indicatie.
Răspunsuri la întrebare
Salut am vrut sa iti scriu cand ai postat dar nu am avut timp.
Programul care l-am facut trebuie adaptat la cerintele exercitiului + mai trebuie sa reformulez prima conditie din backtrack(), dar am sa iti spun ce am facut pana acum:
const int x = rand, y = coloana;
int matrice[x][y] (plina cu valorea 0) //globala
functii: arata(), valideaza(r, c), backtrack(stop, r, c) //r = rand, c = coloana
arata() = arata matricea dupa ce e populata
valideaza(r, c) = returneaza TRUE daca matrice[r][c] == 0, FALSE daca matrice[r][c] != 0;
backtrack(stop, r, c) = stop este un index care se incrementeaza la fiecare reapelare.
in functia backtrack(stop, r, c) am facut conditii (doar if, NU AM FOLOSIT ELSE IF) pentru fiecare coordonate in care poate sari calul luate in ordinea acelor de ceas. Am facut asta scazand/adunand randul si coloana cu (1, 2) sau (2, 1). In momentul in care stop = x * y + 1 afisez matricea.
Am sa scriu si codul mai jos in cazul in care nu ai inteles ce am scris mai sus. Las comentarii in cod :)
(cum spuneam e doar o idee. programul trebuie adaptat pentru cerintele exercitiului)
#include <iostream>
using namespace std;
const int x = 4, y = 5; //x = randuri si y = coloane.
int tabla[x][y] = {}; //tabla sah
bool opreste = false; //variabila asta o folosesc in backtrack() pentru a arata matricea
void arata() //arat matricea
{
for(int r=0; r<x; r++)
{
for(int c=0; c<y; c++)
{
cout << tabla[r][c] << " ";
}
cout << endl;
}
}
bool valideaza(int r, int c) //returneaza ADEVARAT daca tabla[r][c] == 0, FALS daca nu
{
if(tabla[r][c] == 0)
{
return(true);
}
return(false);
}
void backtrack(int stop, int r, int c) //modific valorile din matrice
{
if((stop == x * y + 1) && (!opreste)) //arata matricea. opreste il folosesc pentru a nu afisa de mai multe ori
{ //aici trebuie sa fac niste modificari sa opresc mai eficient functia
arata();
opreste = true;
}
//de aici incep conditiile
if((r - 1 >= 0) && (c - 2 >= 0))
{
if(valideaza(r, c))
{
tabla[r][c] = stop; //modific cifra din tabla[r][c]
backtrack(stop+1, r-1, c-2); //mut calul la coordonatele noi
tabla[r][c] = 0; //daca se blocheaza resetez pozitia tabla[r][c]
}
}
if((r - 2 >= 0) && (c - 1 >= 0))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r-2, c-1);
tabla[r][c] = 0;
}
}
if((r - 2 >= 0) && (c + 1 < y))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r-2, c+1);
tabla[r][c] = 0;
}
}
if((r - 1 >= 0) && (c + 2 < y))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r-1, c+2);
tabla[r][c] = 0;
}
}
if((r + 1 < x) && (c + 2 < y))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r+1, c+2);
tabla[r][c] = 0;
}
}
if((r + 2 < x) && (c + 1 < y))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r+2, c+1);
tabla[r][c] = 0;
}
}
if((r + 2 < x) && (c - 1 >= 0))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r+2, c-1);
tabla[r][c] = 0;
}
}
if((r + 1 < 4) && (c - 2 >= 0))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r+1, c-2);
tabla[r][c] = 0;
}
}
}
int main()
{
backtrack(1, 0, 0);
return(0);
}