In cazul asta, felicitari. Implementarea pare a fi foarte simpla. Ce faci acolo semana cu “breadth-frist search”. O sa revad enuntul, daca gasesc timp.
Cel mai simplu ar fi sa intrerupi executia, daca depasesti limitele, si sa afisezi un mesaj de eroare; sau poti folosi coada standard
<queue> (mai lenta).
...
Am gasit ceva timp si am implementat cum m-am priceput. Nu am participat la vreun concurs, asa ca nu prea stiu care sunt cerintele. Se pare ca este incurajata folosirea variabilelor globale si a numelor criptice. Copiaza codul pe calculatorul tau si vezi ce iese.
#include <time.h>
#include <fstream>
#include <iostream>
using namespace std;
// i este indexul randului; intodeauna
// j este indexul coloanei; intodeauna
// energia maxima
#define EMAX 30000
// numarul maxim de randuri
#define RMAX 200
// numarul maxim de coloane
#define CMAX 200
// energia intiala
int p;
// numarul de randuri
int n;
// numarul de coloane
int m;
// tabla de joc
int c[RMAX][CMAX];
// celulele vizitate
char v[RMAX][CMAX];
// starea robotului
struct t_state
{
int r; // rand
int c; // coloana
int ec; // energie celula
int er; // energie robot
void set( int ar, int ac, int aec, int aer ) { r = ar; c = ac; ec = aec; er = aer; }
};
// coada de stari intermediare
t_state q[RMAX*CMAX]; // datele
int dq; // indexul de extrage (deque)
int eq; // indexul de inserare (enque)
// solutii
int s[CMAX];
int ns; // numar solutii
//
int global_bytes_count()
{
return sizeof( p ) + sizeof( n ) + sizeof( m ) +
sizeof( c ) +
sizeof( v ) +
sizeof( q ) + sizeof( dq ) + sizeof( eq ) +
sizeof( s ) + sizeof( ns );
}
//
bool read()
{
ifstream is( "robot.in" );
if ( ! is )
return false;
if ( ! ( is >> p >> n >> m ) )
return false;
for ( int i = 0; i < n; ++i )
for ( int j = 0; j < m; ++j )
if ( ! ( is >> c[i][j] ) )
return false;
return true;
}
//
bool write()
{
ofstream os( "robot.out" );
if ( ! os )
return false;
if ( ns < 1 )
{
if ( ! ( os << -1 ) )
return false;
}
else
{
for ( int i = 0; i < ns; ++i )
if ( ! (os << s[i] << ' ' ) )
return false;
}
return true;
}
// find_path implementeaza algoritmul "breadth-first search"
// cu o definitie alternativa a adiacentei data de consumul de energie:
// daca consumul este prea mare, celula nu este adiacenta
// (vezi Introduction to Algorithms, Cormen et alii)
bool find_path( int j )
{
// reseteaza celulele vizitate
memset( v, 0, sizeof(v) );
// reseteaza coada
dq = eq = 0;
// adauga pozitia initiala
q[eq++].set( 0, j, c[0][j], p );
// marcheaza pozitia initiala
v[0][j] = 1;
// cat timp coada nu e goala
while ( eq - dq > 0 )
{
// extrage din coada
int tq = dq++;
// daca am ajuns la ultimul rand
if ( q[tq].r >= n - 1 )
return true;
// examineaza celulele adiacente
int i = q[tq].r + 1; // randul adiacent
int pc = ( q[tq].c <= 0 ) ? 0 : -1; // prima coloana relativ la pozitia curenta
int uc = ( q[tq].c <= m - 2 ) ? 1 : 0; // ultima coloana relativ la pozitia curenta
for ( int k = pc; k <= uc; ++k ) // coloanele adiacente relativ la coloana curenta
{
// coloana adiacenta
int j = q[tq].c + k;
// care ar fi energia robotului daca s-ar muta pe celula adiacenta
int er = q[tq].er - abs( c[i][j] - q[tq].ec );
if ( er <= 0 )
continue; // toata energia ar fi consumata: celula nu e "adiacenta"
// celula adiacenta
// daca celula nu este vizitata
if ( ! v[i][j] )
{
// insereaza in coada
q[eq++].set( i, j, c[i][j], er );
// marcheaza
v[i][j] = 1;
}
}
}
// nu a fost gasit niciun drum
return false;
}
//
void run()
{
// initializeaza numarul de solutii
ns = 0;
// cauta drumul pentru fiecare coloana
for ( int j = 0; j < m; ++j )
if ( find_path( j ) )
s[ns++] = j + 1;
}
//
void print_gmem_info()
{
#ifndef NDEBUG
cout << "Memorie globala consumata: " << double( global_bytes_count() ) / 1024 / 1024 << " MB" << endl;
#endif
}
// numarul de executii pentru benchmark
#define XMAX 100000
// afiseaza durata total a executiilor
#define BENCHMARK
int main()
{
print_gmem_info();
if ( ! read() )
{
cerr << "Eroare la citire";
return -1;
}
#ifdef BENCHMARK
clock_t t0 = clock();
for ( int k = 0; k < XMAX; ++k )
#endif
run();
#ifdef BENCHMARK
clock_t d = clock() - t0;
cout << "Durata pentru " << XMAX << " executii: " << double(d)/CLOCKS_PER_SEC << "s" << endl;
#endif
if ( ! write() )
{
cerr << "Eroare la scriere";
return -2;
}
return 0;
}
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena