## 639 - Don't Get Rooked

Moderator: Board moderators

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

### 639 - Don't Get Rooked

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
Try this input...

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

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
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
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore
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; // '.' = 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, 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:
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

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
hi..
is there any special input for this problem??!??!!

my program worked correctly with many i/o. but I got WA...

Tanks.

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

### Re: 639 - Don't Get Rooked

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

That's a critical test case!!!

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

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

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

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

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