260 - Il Gioco dell'X

[keya]

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]

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]

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]

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]

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

removed

[asif_rahman0]

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

so help me plz!!!!!!!!!!!!!!!!!

[emotional blind]

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

[serur]

Indeed, It is floodfill problem - at least I did get it AC with floodfill...
Floodfill from left to right, from top to bottom...

[asif_rahman0]

thnx serur for helping

[Donotalo]

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]

(2, 3) and (3, 2) are not adjacent. Read the problem statement carefully, every cell has only up to 6 neighbours.

[algoJo]

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]

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]

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;
}

[mahade hasan]

cut.....
ACC.......