Page 1 of 2
11405 - Can U Win?
Posted: Sat Jun 21, 2008 3:05 pm
by Chirag Chheda
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..
thanx in advance....
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;
}
Re: 11405 - Can U Win?
Posted: Mon Jun 23, 2008 8:18 am
by Chirag Chheda
Can someone plz reply
Re: 11405 - Can U Win?
Posted: Mon Jun 23, 2008 2:13 pm
by yasuh
try folloing input
Code: Select all
1
2
........
.K....k.
....P...
.....P..
...P....
........
........
.p......
Re: 11405 - Can U Win?
Posted: Mon Jun 23, 2008 2:23 pm
by Chirag Chheda
thank you yasuh for replying.
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.
thanx in advance.
Waiting for ur reply.
Bye
Re: 11405 - Can U Win?
Posted: Mon Jun 23, 2008 3:16 pm
by yasuh
My answer is no.
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...)
Re: 11405 - Can U Win?
Posted: Mon Jun 23, 2008 3:29 pm
by Chirag Chheda
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..
Re: 11405 - Can U Win?
Posted: Mon Jun 23, 2008 4:15 pm
by yasuh
My algorithm is maybe same to you.
However, your program allow you to move your knight n+1 times.
It should be only n times.
Re: 11405 - Can U Win?
Posted: Mon Jun 23, 2008 7:36 pm
by Chirag Chheda
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
Re: 11405 - Can U Win?
Posted: Wed Jun 25, 2008 7:28 pm
by yasuh
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".
Re: 11405 - Can U Win?
Posted: Wed Nov 19, 2008 10:48 pm
by tryit1
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
Re: 11405 - Can U Win?
Posted: Mon Mar 09, 2009 7:55 am
by Chirag Chheda
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
Re: 11405 - Can U Win?
Posted: Mon Mar 09, 2009 6:11 pm
by vahid sanei
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 ?
Re: 11405 - Can U Win?
Posted: Mon Mar 09, 2009 6:43 pm
by Chirag Chheda
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.
Re: 11405 - Can U Win?
Posted: Mon Mar 09, 2009 8:12 pm
by vahid sanei
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
Re: 11405 - Can U Win?
Posted: Tue Mar 10, 2009 7:32 am
by Chirag Chheda
I though you wrote P. I am sorry for that. The answer to your case is yes