infoarena

# include <fstream>
# include <cstdlib>
# define dim 203
# define lim 41412
using namespace std;

struct
{
    short int j,x,y;
    int e;
}v[lim];

short int c[dim][dim],n,m,ener,i,j;
int ind = -1;
bool p[dim] = {false};

void Citeste()
{
    ifstream in("robot.in");
    in >> ener >> n >> m;
    for( i = 1 ; i <= n ; ++i )
        for( j = 1 ; j <= m ; ++j )
    {
        in >> c[i][j];
        if( i == 1 )
        {
            ++ind;
            v[ind].j = j;
            v[ind].x = i;
            v[ind].y = j;
            v[ind].e = ener;
        }
    }
}

void Drum()
{
    short int lin,col,g;
    int e1;
    for( i = 0 ; i <= ind ; ++i )
    {
        lin = v[i].x;
        col = v[i].y;
        g = v[i].j;
        e1 = v[i].e;
        if( lin == n && e1 > 0 )
            p[g] = true;
        if( lin+1 <= n )
        {
            if( e1 - abs(c[lin][col] - c[lin+1][col]) > 0 )
            {
                ++ind;
                v[ind].x = lin+1;
                v[ind].y = col;
                v[ind].j = g;
                v[ind].e = e1 - abs(c[lin][col] - c[lin+1][col]);
            }
            if( e1 - abs(c[lin][col] - c[lin+1][col+1]) > 0 && col+1 <= m )
            {
                ++ind;
                v[ind].x = lin+1;
                v[ind].y = col+1;
                v[ind].j = g;
                v[ind].e = e1 - abs(c[lin][col] - c[lin+1][col+1]);
            }
            if( e1 - abs(c[lin][col] - c[lin+1][col+1]) > 0 && col-1 >= 1 )
            {
                ++ind;
                v[ind].x = lin+1;
                v[ind].y = col-1;
                v[ind].j = g;
                v[ind].e = e1 - abs(c[lin][col] - c[lin+1][col-1]);
            }
        }
    }
}

void Tipar()
{
    bool ok = false;
    ofstream out("robot.out");
    for( i = 1 ; i <= m ; ++i )
        if( p[i] == true )
        {
            ok = true;
            out << i << ' ';
        }
    if( !ok ) out << "-1";
    out.close();
}

main()
{
    Citeste();
    Drum();
    Tipar();
}

#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;
}