## 260 - Il Gioco dell'X

Moderator: Board moderators

keya
New poster
Posts: 3
Joined: Thu Jun 12, 2003 7:27 pm

### 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[0]);
for(w=k=i=0;i<n;i++)
{
if(str[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]

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 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[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[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

rodms
New poster
Posts: 2
Joined: Wed Aug 20, 2003 12:18 am
Location: Rio

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

``````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!

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

### 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!!!!!!!!!!!!!!!!!

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

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

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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.

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

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

### 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?

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

algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am
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?

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 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.

JohnsonWang
New poster
Posts: 4
Joined: Wed May 11, 2011 6:14 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;
}``````