260 - Il Gioco dell'X - TLE

All about problems in Volume II. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

260 - Il Gioco dell'X - TLE

Postby JohnsonWang » Thu Jun 30, 2011 1:25 am

Hi Everyone,

I'm trying to use DFS-based Flood-Fill (for all unvisited 'b' nodes in the first row), however, when I submit my code, it is returning a TLE error.

Can anyone help?

Code: Select all
#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int row_dir[] = { -1, -1, 0, 0, 1, 1 };
int col_dir[] = { -1, 0, -1, 1, 0, 1 };

bool is_in_range( const int& row, const int& col, vector < vector <char> > grid )
{
   if( row >= 0 && col >= 0 && row < grid.size() && col < grid.size() ) return true;
   return false;
}

bool can_connect( const int& cur_row, const int& cur_col, vector < vector <char> >& grid, vector < vector <bool> >& visited )
{
   visited[cur_row][cur_col] = true;
   stack < pair <int, int> > stk;
   stk.push( make_pair( cur_row, cur_col ) );

   while( !stk.empty() )
   {
      pair <int, int> tmp = stk.top();
      stk.pop();

      if( tmp.first == grid.size() - 1 ) return true;

      for( int i = 0; i < 6; i++ )
      {
         int row = tmp.first + row_dir[i];
         int col = tmp.second + col_dir[i];

         if( is_in_range( row, col, grid ) && !visited[row][col] && grid[row][col] == 'b' )
         {
            visited[row][col] = true;
            stk.push( make_pair( row, col ) );
         }
      }
   }

   return false;
}

int main()
{
   int board_size, test_no = 1;
   while( cin >> board_size )
   {
      if( board_size == 0 ) break;

      vector <bool> v_tmp;
      vector <char> g_tmp;

      for( int i = 0; i < board_size; i++ )
      {
         v_tmp.push_back( 0 );
         g_tmp.push_back( 0 );
      }

      vector < vector <bool> > visited;
      vector < vector <char> > grid;
      for( int i = 0; i < board_size; i++ )
      {
         visited.push_back( v_tmp );
         grid.push_back( g_tmp );
      }

      string line;
      for( int row = 0; row < board_size; row++ )
      {
         cin >> line;
         for( int col = 0; col < board_size; col++ )
            grid[row][col] = line[col];
      }

      bool b_wins = false;
      for( int col = 0; col < board_size; col++ )
         if( grid[0][col] == 'b' && !visited[0][col] )
            b_wins = max( b_wins, can_connect( 0, col, grid, visited ) );

      cout << test_no << ' ';
      if( b_wins ) cout << 'B' << endl;
      else cout << 'W' << endl;

      test_no++;
   }

   return 0;
}
JohnsonWang
New poster
 
Posts: 4
Joined: Wed May 11, 2011 6:14 am

Return to Volume II

Who is online

Users browsing this forum: Yahoo [Bot] and 1 guest