639 - Don't Get Rooked

[Tichy]

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]

Try this input...

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

[angga888]

The right answer is 4.

One of possible rook placement:

.R..
RXX.
.XXR
..R.

R=rook.

Using standard backtracking is enough to solve this problem.

Good Luck!

angga888

[ec3_limz]

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]

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]

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]

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]

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]

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]

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]

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]

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