260 - Il Gioco dell'X

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

Moderator: Board moderators

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

260 - Il Gioco dell'X

Post by 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[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!

Post by 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[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?

Post by 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

Post by 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!

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

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

Post by 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

Post by asif_rahman0 » Mon Apr 24, 2006 10:16 pm

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

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

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

Post by 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

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by 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.

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

Post by asif_rahman0 » Wed Apr 26, 2006 8:59 pm

thnx serur for helping
:)

User avatar
Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

260 - misunderstood

Post by 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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by 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.

User avatar
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

Post by 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?

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

Re: 260 - misunderstood

Post by 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.

JohnsonWang
New poster
Posts: 4
Joined: Wed May 11, 2011 6:14 am

260 - Il Gioco dell'X - TLE

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

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 260 -why WAAAAAAAAAA

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

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

Post Reply

Return to “Volume 2 (200-299)”