## 260 - Il Gioco dell'X

Moderator: Board moderators

### 260 - Il Gioco dell'X

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!

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?

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

Well, here goes the code:

[cpp]Got AC.[/cpp]

I've tried with the following test cases:
Code: Select all
`6bwwwwwbwbbbbbbwbbb bbwwbbbbwbwbwwwwwb2wbwb10bwwwbwwwwwbwbbwwwwwwbwbwwwwwwwbwbwbbbbbbbwbwwwwwwbwbbwbbbbbbbwbwbwwwwwbwwwbwbwbbbbbwbbbbbwwwwwwbwwww4bbwbwwbwbwwbwwbb4bbwbwwbwbbwbbwww`

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

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

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

i solved this problem using backtracking..but not flood fill
i think flood is not for this problem

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 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

thnx serur for helping
asif_rahman0
Experienced poster

Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 260 - misunderstood

how does white wins in the first game?

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 can anyone help me to understand this problem?

Donotalo
Learning poster

Posts: 56
Joined: Sat Aug 20, 2005 11:05 am

(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

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?

algoJo
New poster

Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

### Re: 260 - misunderstood

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

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

cut.....
ACC.......
we r surrounded by happiness
need eyes to feel it!