11405 - Can U Win?

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11405 - Can U Win?

Post by Chirag Chheda » Sat Jun 21, 2008 3:05 pm

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
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11405 - Can U Win?

Post by Chirag Chheda » Mon Jun 23, 2008 8:18 am

Can someone plz reply

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

Re: 11405 - Can U Win?

Post by yasuh » Mon Jun 23, 2008 2:13 pm

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?

Post by Chirag Chheda » Mon Jun 23, 2008 2:23 pm

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
New poster
Posts: 7
Joined: Mon Jan 07, 2008 5:34 pm

Re: 11405 - Can U Win?

Post by yasuh » Mon Jun 23, 2008 3:16 pm

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
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11405 - Can U Win?

Post by Chirag Chheda » Mon Jun 23, 2008 3:29 pm

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?

Post by yasuh » Mon Jun 23, 2008 4:15 pm

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
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11405 - Can U Win?

Post by Chirag Chheda » Mon Jun 23, 2008 7:36 pm

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?

Post by yasuh » Wed Jun 25, 2008 7:28 pm

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

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

Re: 11405 - Can U Win?

Post by tryit1 » Wed Nov 19, 2008 10:48 pm

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?

Post by Chirag Chheda » Mon Mar 09, 2009 7:55 am

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

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

Re: 11405 - Can U Win?

Post by vahid sanei » Mon Mar 09, 2009 6:11 pm

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?

Post by Chirag Chheda » Mon Mar 09, 2009 6:43 pm

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.

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

Re: 11405 - Can U Win?

Post by vahid sanei » Mon Mar 09, 2009 8:12 pm

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?

Post by Chirag Chheda » Tue Mar 10, 2009 7:32 am

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

Post Reply

Return to “Volume 114 (11400-11499)”