Could you help me with this problem? I receive SIGABRT. Obviously one of the asserts fires. If I remove all asserts I get SIGSEGV which is what I expect. But I can't see how any input can lead to SIGABRT. I tried different input parameters but I couldn't find any that can crash this program.
[cpp]
// valladolid problem #10401
//
http://online-judge.uva.es/p/v104/10401.html
#include <iostream>
#include <vector>
#include <memory>
#include <functional>
#include <algorithm>
#include <string>
#include <exception>
#include <cassert>
using namespace std;
enum field_val
{
field_occupied = -1
, field_init = 1
};
class board
{
public:
board( int size )
: m_size( size )
, m_queens( size )
, m_board( size )
, m_good( true )
{
for ( int i = 0; i < m_size; ++i )
m_board[ i ].resize( m_size );
}
bool good() const
{
return m_good;
}
void set_queen( int file, int rank )
{
if ( ! good() )
return;
if ( m_board[ file ][ rank ] == field_occupied )
{
m_good = false;
return;
}
if ( rank >= m_size )
{
m_good = false;
return;
}
assert( file >= 0 && file < m_size );
assert( rank >= 0 );
m_queens[ file ] = true;
fill( file );
fill( file - 1, rank - 1, rank + 2 );
fill( file + 1, rank - 1, rank + 2 );
}
void set_initial_vals()
{
int file = find_unoccupied( m_size - 1 );
if ( file < 0 )
return;
for ( int rank = 0; rank < m_size; ++rank )
{
if ( m_board[ file ][ rank ] != field_occupied )
m_board[ file ][ rank ] = field_init;
}
}
long long compute_positions()
{
if ( ! good() )
return 0;
int file = find_unoccupied( m_size - 2 );
if ( file < 0 )
return 1; // if all files are occupied than
// there is only one valid position
int last_processed_file = -1;
for ( ; file >= 0; --file )
{
if ( ! m_queens[ file ] )
process_file( last_processed_file = file );
}
assert( last_processed_file != -1 );
long long positions = 0;
for ( int rank = 0; rank < m_size; ++rank )
{
if ( m_board[ last_processed_file ][ rank ] != field_occupied )
positions += m_board[ last_processed_file ][ rank ];
}
return positions;
}
private:
int find_unoccupied( int start_file )
{
int file = start_file;
while ( file >= 0 && m_queens[ file ] )
--file;
return file;
}
void process_file( int file )
{
assert( file < m_size - 1 );
assert( ! m_queens[ file ] );
#ifdef TRACE
cout << file << endl;
#endif
for ( int rank = 0; rank < m_size; ++rank )
{
if ( m_board[ file ][ rank ] == field_occupied )
continue;
int next_file = file + 1;
while ( m_queens[ next_file ] )
{
++next_file;
assert( next_file < m_size );
}
long long field_val = 0;
for ( int next_rank = 0; next_rank < m_size; ++next_rank )
{
if ( ( next_file > file + 1 || next_rank < rank - 1 || next_rank > rank + 1 )
&& m_board[ next_file ][ next_rank ] != field_occupied )
{
field_val += m_board[ next_file ][ next_rank ];
}
}
m_board[ file ][ rank ] = field_val;
#ifdef TRACE
cout << file << ':' << rank << "->" << field_val << ' '; #endif
}
#ifdef TRACE
cout << endl;
#endif
}
void fill( int file, int start_rank = 0 )
{
fill_with( field_occupied, file, start_rank );
}
void fill( int file, int start_rank, int end_rank )
{
fill_with( field_occupied, file, start_rank, end_rank );
}
void fill_with( long long val, int file, int start_rank = 0 )
{
if ( start_rank < 0 )
start_rank = 0;
fill_with( val, file, start_rank, m_size );
}
void fill_with( long long val, int file, int start_rank, int end_rank )
{
if ( file < 0 ) return;
if ( file >= m_size ) return;
if ( start_rank < 0 )
start_rank = 0;
if ( end_rank > m_size )
end_rank = m_size;
for ( int i = start_rank; i < end_rank; ++i )
m_board[ file ][ i ] = val;
}
private:
board( board const & ); // undefined
board & operator=( board const & ); // undefined
private:
int m_size;
vector< bool > m_queens;
vector< vector< long long > > m_board;
bool m_good;
};
struct initializer : unary_function< void, char > {
initializer( board & brd )
: m_board( brd )
, m_cur_file( 0 )
{}
void operator()( char ch )
{
if ( isdigit( ch ) )
m_board.set_queen( m_cur_file, ch - '1' );
else if ( ch >= 'A' && ch <= 'F' )
m_board.set_queen( m_cur_file, ch - 'A' + 10 );
else if ( ch >= 'a' && ch <= 'f' )
m_board.set_queen( m_cur_file, ch - 'a' + 10 );
++m_cur_file;
}
private:
board & m_board;
int m_cur_file;
};
auto_ptr< board > read_input()
{
string input;
while ( input.empty() )
cin >> input;
board * brd = new board( input.size() );
for_each( input.begin(), input.end(), initializer( *brd ) );
return auto_ptr< board >( brd );
}
int main()
{
cin.exceptions( ios::eofbit | ios::badbit | ios::failbit );
cout.exceptions( ios::eofbit | ios::badbit | ios::failbit );
try
{
for (;;)
{
auto_ptr< board > brd( read_input() );
brd->set_initial_vals();
cout << brd->compute_positions() << endl;
}
}
catch ( exception & e )
{
if ( ! cin.eof() )
{
cerr << "error: " << e.what() << endl;
return 1;
}
}
}
[/cpp]
