639 - Don't Get Rooked

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

Moderator: Board moderators

Post Reply
Tichy
New poster
Posts: 1
Joined: Sat Sep 21, 2002 11:42 am
Location: Argentina

639 - Don't Get Rooked

Post by Tichy » Sat Sep 21, 2002 11:45 am

I'm getting WA on 639. To be honest I'm not 100% sure that my algorithm actually solves the problem, so I'm looking for tricky inputs.

My prog works by counting (and storing) all the positions invalidated by putting a rook in each position. Then it starts putting rooks in the positions that would invalidate less. When all positions are either occupied by a rook or invalidated by one, it's done, and returns the count of rooks it successfuly positioned.

So, I'm looking for an input that would make this algorithm answer wrong, or any other insight you might wanna share about the problem.

--Tichy

chfgress
New poster
Posts: 3
Joined: Tue Jun 03, 2003 2:55 am

Post by chfgress » Thu Jun 19, 2003 2:12 am

Try this input...

4
....
.xx.
.xx.
....

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Thu Jun 19, 2003 7:21 pm

The right answer is 4. :D

One of possible rook placement:
.R..
RXX.
.XXR
..R.
R=rook.

Using standard backtracking is enough to solve this problem.

Good Luck! :)

angga888 :lol:

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

Post by ec3_limz » Fri Jun 20, 2003 7:28 pm

Using standard backtracking is enough to solve this problem.
I am actually quite surprised that greedy algorithm works for this problem.

My greedy algorithm works like this.

1. For each position p on the board, find the number of positions that a rook placed at p can attack. Let a[ p ] be the number of positions a rook placed at position p can attack.

2. Repeatedly place a rook at position q where a[ q ] is minimum. Cancel all positions that a rook at position q can attack.

3. Count the number of rooks placed and output.

In case you are interested here is the code I used to submit to the Online Judge.

[cpp]#include <stdio.h>

char board[4][5]; // '.' = space, 'X' = wall, 'u' = used
int side;

int controlsize(int x, int y) {
int size = 1, i;

for (i = x - 1; i >= 0 && board[y] != 'X'; i--, size++);
for (i = y + 1; i < side && board[x] != 'X'; i++, size++);
for (i = x + 1; i < side && board[y] != 'X'; i++, size++);
for (i = y - 1; i >= 0 && board[x] != 'X'; i--, size++);

return size;
}

void update(int x, int y) {
int i;

board[x][y] = 'u';
for (i = x - 1; i >= 0 && board[y] != 'X'; i--)
board[y] = 'u';
for (i = y + 1; i < side && board[x] != 'X'; i++)
board[x] = 'u';
for (i = x + 1; i < side && board[y] != 'X'; i++)
board[y] = 'u';
for (i = y - 1; i >= 0 && board[x][i] != 'X'; i--)
board[x][i] = 'u';
}

int main() {
int controls[4][4], rooks, min, min_x, min_y;
int i, j;

while (true) {
scanf("%d", &side);
if (side == 0)
break;
for (i = 0; i < side; i++)
scanf("%s", &board[i]);

for (i = 0; i < side; i++)
for (j = 0; j < side; j++)
if (board[i][j] == '.')
controls[i][j] = controlsize(i, j);

rooks = 0;
while (true) {
min = 100;
for (i = 0; i < side; i++)
for (j = 0; j < side; j++)
if (board[i][j] == '.' && controls[i][j] < min) {
min = controls[i][j];
min_x = i;
min_y = j;
}
if (min == 100)
break;
update(min_x, min_y);
rooks++;
}
printf("%d\n", rooks);
}

return 0;
}
[/cpp]

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik » Fri Jul 01, 2005 12:10 pm

I am actually quite surprised that greedy algorithm works for this problem.
I found a counterexample, although it is larger as the specified input contraints:

Code: Select all

###...
###...
##..##
...###
..####
..####
If I understood your strategy correctly, then it would first choose the "middle" field, which in the end will give 5 Rooks. But you can obtain 6 Rooks omitting that field (especially you use the two adjacent squares to place rooks).

Nevertheless, this problem can be transformed into a bipartite matching. Consider all consecutive dots in horizontal and vertical direction as defining a node. Now every free (dot) place occupies two of such nodes, one vertical and one horizontal, when a rook is placed there. So you just insert all free squares as edges between the corresponding nodes and then determine the maximum matching.

Bye, Erik :)

swpeng
New poster
Posts: 5
Joined: Sun Jun 12, 2005 2:14 pm

639 -WA

Post by swpeng » Tue Oct 25, 2005 10:33 am

I got WA on 639, and I have tried a lot of cases. Can anyone help me with my problem or provide me inputs?

Code: Select all

#include<iostream>

using namespace std;

const int mmax=5;
int mapmax;
char map[mmax+1][mmax+1];
int dotmax;

void track(int y,int x,char ch){
	int i;
	//y->i
	for(i=y-1;i>=0;i--){
		if(map[i][x]=='X' || map[i][x]=='O')
			break;
		map[i][x]=ch;
	}
	for(i=y+1;i<=mapmax;i++){
		if(map[i][x]=='X' || map[i][x]=='O')
			break;
		map[i][x]=ch;
	}
	//x->i
	for(i=x-1;i>=0;i--){
		if(map[y][i]=='X' || map[y][i]=='O')
			break;
		map[y][i]=ch;
	}
	for(i=x+1;i<=mapmax;i++){
		if(map[y][i]=='X' || map[y][i]=='O')
			break;
		map[y][i]=ch;
	}
}

void log(int dots){
	if(dots>dotmax)
		dotmax=dots;
}

void dfs(int y,int x,int dots){
	log(dots);
	for(;y<=mapmax;y++){
		for(;x<=mapmax;x++){
			if(map[y][x]=='.'){
				map[y][x]='O';
				track(y,x,'-');
				dfs(y,x,dots+1);
				map[y][x]='.';
				track(y,x,'.');
			}
		}
		x=0;
	}
}

int main(){
	int x,y;
	while(cin>>mapmax){
		//last case
		if(mapmax==0)
			break;
		//len->limit
		mapmax--;
		//default
		for(y=0;y<=mmax;y++){
			for(x=0;x<=mmax;x++){
				map[y][x]='.';
			}
		}
		dotmax=0;
		//input
		for(y=0;y<=mapmax;y++){
			cin>>map[y];
		}
		dfs(0,0,0);
		cout<<dotmax<<endl;
	}
	return 0;
}

RED-C0DE
New poster
Posts: 16
Joined: Mon Mar 26, 2007 6:47 pm

Post by RED-C0DE » Mon May 14, 2007 1:43 pm

hi..
is there any special input for this problem??!??!!

my program worked correctly with many i/o. but I got WA...
please help me.. I'm a novice..

Tanks.

multisystem
New poster
Posts: 4
Joined: Fri Oct 02, 2009 4:06 pm

Re: 639 - Don't Get Rooked

Post by multisystem » Wed Aug 04, 2010 1:07 am

some useful test cases

Input
4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
3
...
...
.XX
3
X.X
X.X
X.X
4
X.X.
.X.X
X.X.
.X.X
4
.X.X
X.X.
.X.X
X.X.
4
....
....
....
X.X.
0
Output
5
1
5
2
4
3
1
8
8
4

back_tracker
New poster
Posts: 9
Joined: Sun Jun 19, 2011 12:03 am

Re: 639 - Don't Get Rooked

Post by back_tracker » Thu Jun 23, 2011 4:54 am

That's a critical test case!!!

4
..X.
.X..
..X.
...X

the answer should be 6
I am getting 7, dunno why. i am gonna solve the problem tomorrow. For now, I am so sleepy so gd night everyone =)

back_tracker
New poster
Posts: 9
Joined: Sun Jun 19, 2011 12:03 am

Re: 639 - Don't Get Rooked

Post by back_tracker » Thu Jun 23, 2011 1:00 pm

Hi,

This is an automated response from UVa Online Judge.

Your submission with number 8980068 for the problem 639 - Don't Get Rooked has succeeded with verdict Accepted.


Congratulations! Now it is time to try a new problem.


Best regards,

The UVa Online Judge team


WOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOHOOOOOOO

samoel_stt
New poster
Posts: 8
Joined: Mon Jun 16, 2014 11:59 pm

Re: 639 - Don't Get Rooked

Post by samoel_stt » Fri Jun 20, 2014 7:11 pm

I have tried different inputs for the problem and it gives the right answer, but i get WA all the times. Is there anything wrong? or there is a special input for the problem, because what if i read a character that is different to '.' or 'X'? Do i have to consider them as a block or a free space?
Here's the code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define MAX 4
char tab[MAX][MAX];
void leerTab(char tab[MAX][MAX], int tam){
    int i,j;
    for(i=0;i<tam;i++)
        for(j=0;j<tam;j++){
            int car;
            scanf(" %c",&tab[i][j]);
       }
            
}
int max(int value1, int value2){
    if (value1>value2) return value1;
    return value2;
}
void buscaPo(int fil, int col,int tam,int* sx, int *sy){
   *sx = fil+1;
   *sy = col;
   if (*sx == tam){
       *sx = 0;
       *sy = col+1;
   }
}
int isSafe(int fil, int col,char tab[MAX][MAX], int tam){
    int i;
    if (tab[fil][col] == 'X' || tab[fil][col] == 'T')
        return 0;
    for(i=col-1;i>=0;i--){
        if (tab[fil][i] == 'X') break;
        if (tab[fil][i] == 'T') return 0;
    }
    for(i=fil-1;i>=0;i--){
       if (tab[i][col] == 'X') break;
       if (tab[i][col] == 'T') return 0;
    }
    return 1;    
}
void llena(int fil,int col,int tam, char tab[MAX][MAX],int *ntorres,int *maxi){
    if (col == tam){
        *maxi = max(*ntorres,*maxi);
        return;
    }
    int sig_x,sig_y;
    
    buscaPo(fil,col,tam,&sig_x,&sig_y);
    if ( isSafe(fil,col,tab,tam) ){
        tab[fil][col] = 'T';
        (*ntorres)++;
        llena(sig_x,sig_y,tam,tab,ntorres,maxi);
        tab[fil][col] = '.';
        (*ntorres)--;
    }
    llena(sig_x,sig_y,tam,tab,ntorres,maxi);
}
int main(int argc, char** argv) {
    int tam;
   while ( scanf("%d",&tam) != EOF ){
        leerTab(tab,tam);
        int torres = 0, mtorres = 0;
        llena(0,0,tam,tab,&torres,&mtorres);
        printf("%d\n",mtorres);
    }
    return 0;
}

samoel_stt
New poster
Posts: 8
Joined: Mon Jun 16, 2014 11:59 pm

Re: 639 - Don't Get Rooked

Post by samoel_stt » Fri Jun 20, 2014 7:50 pm

Forget my last post, it was just because i was considering negative inputs. Added an if ( tam > 0) and got AC.

Post Reply

Return to “Volume 6 (600-699)”