11405 - Can U Win?

[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;
}

[Chirag Chheda]

Can someone plz reply

[yasuh]

try folloing input

Code: Select all

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

[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

[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...)

[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..

[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.

[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

[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".

[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

[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

[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 ?

[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.

[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

[Chirag Chheda]

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