## 11405 - Can U Win?

Moderator: Board moderators

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### 11405 - Can U Win?

Can some kind person please post some test cases for this prob or check his output with mine..i dont know where i m going wrong..

Code: Select all

``````#include<iostream>

using namespace std;

char arr[8][8];
int chk[8][8];
int moves;

void floodfill(int i,int j,int m,int c)
{
if(c==0)
return;

if(arr[i][j]=='P')
c--;

arr[i][j]='.';
chk[i][j]=m;

if(i-2>=0 && j+1<=7 && (arr[i-2][j+1]=='P' || arr[i-2][j+1]=='.') && chk[i-2][j+1]>m && m<moves)
floodfill(i-2,j+1,m+1,c);

if(i-2>=0 && j-1>=0 && (arr[i-2][j-1]=='P' || arr[i-2][j-1]=='.') && chk[i-2][j-1]>m && m<moves)
floodfill(i-2,j-1,m+1,c);

if(i+2<=7 && j-1>=0 && (arr[i+2][j-1]=='P' || arr[i+2][j-1]=='.') && chk[i+2][j-1]>m && m<moves)
floodfill(i+2,j-1,m+1,c);

if(i+2<=7 && j+1<=7 && (arr[i+2][j+1]=='P' || arr[i+2][j+1]=='.') && chk[i+2][j+1]>m && m<moves)
floodfill(i+2,j+1,m+1,c);

if(i-1>=0 && j-2>=0 && (arr[i-1][j-2]=='P' || arr[i-1][j-2]=='.') && chk[i-1][j-2]>m && m<moves)
floodfill(i-1,j-2,m+1,c);

if(i-1>=0 && j+2<=7 && (arr[i-1][j+2]=='P' || arr[i-1][j+2]=='.') && chk[i-1][j+2]>m && m<moves)
floodfill(i-1,j+2,m+1,c);

if(i+1<=7 && j-2>=0 && (arr[i+1][j-2]=='P' || arr[i+1][j-2]=='.') && chk[i+1][j-2]>m && m<moves)
floodfill(i+1,j-2,m+1,c);

if(i+1<=7 && j+2<=7 && (arr[i+1][j+2]=='P' || arr[i+1][j+2]=='.') && chk[i+1][j+2]>m && m<moves)
floodfill(i+1,j+2,m+1,c);
}

int main()
{
int t;
cin>>t;

while(t--)
{
int i,j,k,x,y;
cin>>moves;

int count=0;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
chk[i][j]=moves+2;
cin>>arr[i][j];
if(arr[i][j]=='k')
{
x=i;
y=j;
}
if(arr[i][j]=='P')
count++;
}
}
bool f=0;
floodfill(x,y,0,count);

for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(arr[i][j]=='P')
{
f=1;
break;
}
}
}

if(f)
cout<<"No"<<endl;

else
cout<<"Yes"<<endl;
}

system("pause");
return 0;
}
``````

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11405 - Can U Win?

yasuh
New poster
Posts: 7
Joined: Mon Jan 07, 2008 5:34 pm

### Re: 11405 - Can U Win?

try folloing input

Code: Select all

``````1
2
........
.K....k.
....P...
.....P..
...P....
........
........
.p......
``````

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11405 - Can U Win?

my answer to ur input is Yes.
Could you plz post some more test cases so that i can find my mistake and rectify it.

Bye

yasuh
New poster
Posts: 7
Joined: Mon Jan 07, 2008 5:34 pm

### Re: 11405 - Can U Win?

I think you can find your mistake with that input.
(Hint: There are 3 'p's in the input, but you can move your knight at most 2 times...)

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11405 - Can U Win?

Well it seems that i am wrongly interpreting the question..
Can u please share algo or give me some hint of how to solve it.

Thnx..

yasuh
New poster
Posts: 7
Joined: Mon Jan 07, 2008 5:34 pm

### Re: 11405 - Can U Win?

My algorithm is maybe same to you.
It should be only n times.

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11405 - Can U Win?

Well can u tell me if there is only one move and we have 2 pawns which are reachable from the present position of the knight then by the algo which i have implemented the answer shud be yes.. but according to you the answer should be no...

The following code checks all possible 8 moves for single n.

Code: Select all

``````void floodfill(int i,int j,int m,int c)
{
if(c==0)
return;

if(arr[i][j]=='P')
c--;

arr[i][j]='.';
chk[i][j]=m;

if(i-2>=0 && j+1<=7 && (arr[i-2][j+1]=='P' || arr[i-2][j+1]=='.') && chk[i-2][j+1]>m && m<moves)
floodfill(i-2,j+1,m+1,c);

if(i-2>=0 && j-1>=0 && (arr[i-2][j-1]=='P' || arr[i-2][j-1]=='.') && chk[i-2][j-1]>m && m<moves)
floodfill(i-2,j-1,m+1,c);

if(i+2<=7 && j-1>=0 && (arr[i+2][j-1]=='P' || arr[i+2][j-1]=='.') && chk[i+2][j-1]>m && m<moves)
floodfill(i+2,j-1,m+1,c);

if(i+2<=7 && j+1<=7 && (arr[i+2][j+1]=='P' || arr[i+2][j+1]=='.') && chk[i+2][j+1]>m && m<moves)
floodfill(i+2,j+1,m+1,c);

if(i-1>=0 && j-2>=0 && (arr[i-1][j-2]=='P' || arr[i-1][j-2]=='.') && chk[i-1][j-2]>m && m<moves)
floodfill(i-1,j-2,m+1,c);

if(i-1>=0 && j+2<=7 && (arr[i-1][j+2]=='P' || arr[i-1][j+2]=='.') && chk[i-1][j+2]>m && m<moves)
floodfill(i-1,j+2,m+1,c);

if(i+1<=7 && j-2>=0 && (arr[i+1][j-2]=='P' || arr[i+1][j-2]=='.') && chk[i+1][j-2]>m && m<moves)
floodfill(i+1,j-2,m+1,c);

if(i+1<=7 && j+2<=7 && (arr[i+1][j+2]=='P' || arr[i+1][j+2]=='.') && chk[i+1][j+2]>m && m<moves)
floodfill(i+1,j+2,m+1,c);
}
``````
Let me know if I am wrong...

Bye

yasuh
New poster
Posts: 7
Joined: Mon Jan 07, 2008 5:34 pm

### Re: 11405 - Can U Win?

I'm sorry that I misunderstood your algorithm. It's not same to mine. and I think you have misread problem statement.
Problem statement says, "your sister will lose if and only if she loses all her pawns" and "Can U Ensure your Win making not more than n legal (or illegal?) moves".
This means that you should return "Yes" only when "there's a sequence of moves(at most n moves) which enable you to get ALL pawns in that sequence of moves".
For example, if your knight is at (1,1) and sister's 2 pawns are at (2,3) and (3,2), you need 3 moves to take these pawns. (one example of the 3 moves is (1,1)->(2,3)->(1,1)->(3,2).)
So the my previous test case (Posted on Mon Jun 23, 2008 2:13 pm) need 4 moves to take all pawns( (2,7)->(3,5)->(5,4)->(4,6) etc. ), so the answer for that case should be "No".

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 11405 - Can U Win?

testcases

Code: Select all

``````10
13
...P....
.K...k..
...pP..p
P...pPp.
...P....
........
........
.p....P.

13
...P....
.K...k..
...PP..P
P...PPP.
...P....
........
........
.p....P.

17
...P....
.K...k..
...PP..P
P...PPP.
...P....
........
........
.P....P.

25
...P....
.K...k..
...PP..P
P...PPP.
...P....
........
........
.P....P.

3
........
.K...k..
...P...P
.....p..
........
........
........
........

4
........
.K......
........
........
...k....
.P...p..
p.p.p...
P.P.....

19
........
.K.P....
pppppppp
pppppppp
...k....
.P...p..
p.p.p...
P.P.....

0
........
.K......
........
........
...k....
........
........
........

0
........
.K......
........
........
...k....
........
........
........
2
...P....
.K......
..p.....
k.......
........
........
........
........
``````
My AC output

Code: Select all

``````Yes
No
No
Yes
Yes
Yes
No
Yes
Yes
No
``````

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11405 - Can U Win?

Some of the above test cases are wrong as there can be a maximum of 8 P's or 8 p's in a chessboard. So dont get confused

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 11405 - Can U Win?

It`s not very important if number of p(coins of his sister) be 8 or more

--
however i can`t solve this problem still ,
dfs is good method for this problem ?
Impossible says I`m possible

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11405 - Can U Win?

It's very important because if the number of P increases then the time complexity will also increase.
Anyways I used BFS with some memorization to solve it.

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 11405 - Can U Win?

i said p , not P

--
my code doesnt pass this test case

Code: Select all

``````1
6
...P..P.
.K...k..
...pP..P
....pPp.
...P....
........
........
.p......
``````
this is Yes i think
Impossible says I`m possible

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11405 - Can U Win?

I though you wrote P. I am sorry for that. The answer to your case is yes