260 - Il Gioco dell'X

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

Postby keya » Thu Jun 12, 2003 9:49 pm

Why WA? :(

[cpp]#include<stdio.h>
#define N 201

long long n, i, j, k, w, count=0;
char str[N][N];

void main(void)
{
while(scanf("%lld",&n)&&n)
{
for(i=0;i<n;i++)
scanf("%s",&str[i][0]);
for(w=k=i=0;i<n;i++)
{
if(str[i][0]=='w')
{
for(j=i,k=0;;)
{
if(str[j][k+1]=='w')
k++;
else if(str[j+1][k+1]=='w')
j++,k++;
else
break;
if((k+1)>=n)
{
w = 1;
break;
}
}
if(w)
{
w = 1;
break;
}
}
}
if(w)
printf("%lld W\n",++count);
else
printf("%lld B\n",++count);
}
}[/cpp]
keya
New poster
 
Posts: 3
Joined: Thu Jun 12, 2003 7:27 pm

hi, it's me again, with 260!

Postby oriol78 » Thu Jul 24, 2003 4:11 pm

i'm sure that my solution is correct but obiously i'm wrong, hehe
[cpp]

/* @BEGIN_OF_SOURCE_CODE */

#include <iostream>
#include <vector>
#include <map>
#include <utility>
using namespace std;

map<pair<int,int>, bool> memDyn;
map<pair<int,int>, bool>::iterator it;
vector<vector<char> > board(200,vector<char>(200));

bool hiHaCami(int fila, int columna, int tam)
{
it = memDyn.find(make_pair(fila,columna));
if(it != memDyn.end())
return it->second;
if(columna == tam-1)
return true;
if(fila-1 >= 0 && board[fila-1][columna] == 'w')
{
if(hiHaCami(fila-1,columna,tam))
{
memDyn[make_pair(fila,columna)] = true;
return true;
}
}
if(fila+1 < tam && columna+1 < tam && board[fila+1][columna+1] == 'w')
{
if(hiHaCami(fila+1,columna+1,tam))
{
memDyn[make_pair(fila,columna)] = true;
return true;
}
}
if(columna+1 < tam && board[fila][columna+1] == 'w')
{
if(hiHaCami(fila,columna+1,tam))
{
memDyn[make_pair(fila,columna)] = true;
return true;
}
}
memDyn[make_pair(fila,columna)] = false;
return false;
}

bool white(int tam)
{
memDyn.clear();
for(int i = 0; i < tam; i++)
{
if(board[i][0] == 'w')
{
if(hiHaCami(i,0,tam))
return true;
}
}
return false;
}

char proces(int tam)
{
for(int i = 0; i < tam; i++)
{
for(int j = 0; j < tam; j++)
cin >> board[i][j];
}
if(white(tam))
return 'W';
else
return 'B';
}

int main()
{
long int tam, count = 1;
cin >> tam;
while(tam != 0)
{
cout << count++ << " " << proces(tam) << endl;
cin >> tam;
}
return 0;
}
/* @END_OF_SOURCE_CODE */
[/cpp]

this is my WA code, can anybody found my mistake plz? thx :-)
oriol78
New poster
 
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

260 - Il Gioco dell'X DFS?

Postby rodms » Wed Aug 20, 2003 12:26 am

I'm using a simple depth first search to get a path of b's from top to bottom. I've tried in many test cases and it give's me the right answers.

I can't see what's wrong! I also tried looking for a w's path, but got WA. Is there any other algorythm that would work for this simple problem? Some test cases would help too.
rodms
New poster
 
Posts: 2
Joined: Wed Aug 20, 2003 12:18 am
Location: Rio

Postby rodms » Sun Aug 31, 2003 8:04 am

Well, here goes the code:

[cpp]Got AC.[/cpp]

I've tried with the following test cases:
Code: Select all
6
bwwwww
bwbbbb
bbwbbb
bbwwbb
bbwbwb
wwwwwb
2
wb
wb
10
bwwwbwwwww
bwbbwwwwww
bwbwwwwwww
bwbwbbbbbb
bwbwwwwwwb
wbbwbbbbbb
bwbwbwwwww
bwwwbwbwbb
bbbwbbbbbw
wwwwwbwwww
4
bbwb
wwbw
bwwb
wwbb
4
bbwb
wwbw
bbwb
bwww


It seems to give me the right answers to this tests... but I keep getting WA!
rodms
New poster
 
Posts: 2
Joined: Wed Aug 20, 2003 12:18 am
Location: Rio

260..........help me plz

Postby asif_rahman0 » Sat Apr 22, 2006 8:54 pm

i used flood fill ....but i m getting TLE...how:(??????
where is my fault?

removed
Last edited by asif_rahman0 on Wed Apr 26, 2006 8:56 pm, edited 1 time in total.
asif_rahman0
Experienced poster
 
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Postby asif_rahman0 » Mon Apr 24, 2006 10:16 pm

still i didnt find anything...
& also nobody reply me at all.

so help me plz!!!!!!!!!!!!!!!!!
asif_rahman0
Experienced poster
 
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Postby emotional blind » Tue Apr 25, 2006 7:28 pm

your code is very difficult to read and understand
its better to discuss about your algorithm..
try to explain your algorithm..

i solved this problem using backtracking..but not flood fill
i think flood is not for this problem
User avatar
emotional blind
A great helper
 
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh

Postby serur » Wed Apr 26, 2006 11:13 am

Indeed, It is floodfill problem - at least I did get it AC with floodfill...
Floodfill from left to right, from top to bottom...
Last edited by serur on Sat Apr 14, 2012 3:34 pm, edited 1 time in total.
serur
A great helper
 
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Postby asif_rahman0 » Wed Apr 26, 2006 8:59 pm

thnx serur for helping
:)
asif_rahman0
Experienced poster
 
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

260 - misunderstood

Postby Donotalo » Sat Sep 16, 2006 9:09 pm

how does white wins in the first game?

Image

there is more than one path from row 1 to row 4 for black:
(1, 2) -> (2, 3) -> (3, 2) -> (4, 1)
or
(1, 4) -> (2, 3) -> (3, 2) -> (4, 1)

same for the 2nd game. it seems to me that everyone is winning the game :oops: can anyone help me to understand this problem?
Image
User avatar
Donotalo
Learning poster
 
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

Postby mf » Sat Sep 16, 2006 9:42 pm

(2, 3) and (3, 2) are not adjacent. Read the problem statement carefully, every cell has only up to 6 neighbours.
mf
Guru
 
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

Postby algoJo » Wed Jan 31, 2007 3:07 pm

Hi all
I've got accepted in this problem
but there is something that make me confius...
first I got TLE because:

Code: Select all
char line[201],arr[200][201];
int I,i;
while(1)
{
     gets(line);
     sscanf(line,"%d",&I);
     if(!I) break;
     for(i=0;i<I;i++)
           gets(arr[i]);
}


and got accepted by changing:

Code: Select all
char temp,arr[200][201];
int I,i;

while(1)
{
     scanf("%d",&I);
     scanf("%c",&temp);
     if(!I) break;
     for(i=0;i<I;i++)
           gets(arr[i]);
}


what's the differences?
User avatar
algoJo
New poster
 
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

Re: 260 - misunderstood

Postby BUET » Tue Nov 30, 2010 7:24 am

After taking integer input,when you press 'enter', then this newline is counted as first row of grid. So after taking integer, you can use getchar() to ignore newline.
BUET
New poster
 
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

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

Re: 260 -why WAAAAAAAAAA

Postby mahade hasan » Wed Aug 08, 2012 10:32 am

cut.....
ACC.......
we r surrounded by happiness
need eyes to feel it!
User avatar
mahade hasan
Learning poster
 
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh


Return to Volume II

Who is online

Users browsing this forum: No registered users and 2 guests