-3
$\begingroup$

https://www.interviewstreet.com/challenges/dashboard/#problem/4f1c88e0dec8a

Fairy Chess (35 Points)

You have a $N \times N$ chess board. An $S$-leaper is a chess piece which can move from square $(x_1,y_1)$ on the board to any other square $(x_2,y_2)$ if $|x_1 - x_2| + |y_1 - y_2| \le S$. The chess board may also contain some pawns. The leaper cannot land on the same square as a pawn. In how many ways can a leaper move $M$ times on the board?

Input: The first line contains the number of test cases $T$. $T$ cases follow. Each case contains integers $N$, $M$ and $S$ on the first line. The next $N$ lines contains $N$ characters each. The $i$th character on the $j$th line is a . if the corresponding chess square is empty, P if there is a pawn, or L if the leaper is situated on that square.

Output: For each case, output the number of ways the leaper can make $M$ moves. Output each answer modulo 1000000007.

Constraints: $$\begin{gather} 1 \le T \le 10 \\ 1 \le S \le N \le 200 \\ 1 \le M \le 200 \\ \end{gather}$$ There will be exactly one L character on the board.

Sample Input:

3
4 1 1
....
.L..
.P..
....
3 2 1
...
...
..L
4 3 2
....
...L
..P.
P...

Sample Output:

4
11
385

I wrote a DP solution but with O(N^5).

Psuedocode for ways function:

Memoize[Xmax][Ymax][Nmax];

ways(int X, int Y, int M) // (X,Y) current co-ordinates and M is number of moves to make
{
    if(Memoize[X][Y][M] != -1) // != -1 means we already have the result
        return Memoize[X][Y][M];
    sum=0;
    for all (u,v) such that |X-u| + |Y-v| <= S
        sum += ways(u, v, M-1);

    Memoize[X][Y][M] = sum;
    return sum;

}

Code:

/* Enter your code here. Read input from STDIN. Print output to STDOUT */

#include <stdio.h>
#include <stdlib.h>

long ways(long ***DP, char **Chess, int X, int Y, int S, int N, int M);

int main()
{
    int T;
    scanf("%d", &T);
    while(T>0)
    {
        int N, M, S;
        scanf("%d", &N);
        scanf("%d", &M);
    scanf("%d", &S);
        long ***DP = (long ***) malloc(sizeof(long **) * N);
        int i,j,k;
        char **Chess = (char **)malloc(sizeof(char *) *N);
        int Xstart;
        int Ystart; //printf("N=%dM=%dS=%d\n", N, M, S);
        for(i=0;i<N;i++)
        {
        Chess[i] = (char *)malloc(sizeof(char) *N);
        DP[i] = (long **)malloc(sizeof(long *) * N);
            for(j=0;j<N;j++)
            {   //printf("i=%dj=%d\n", i, j);
        DP[i][j] = (long *)malloc(sizeof(long) *(M+1));
                char a;
                scanf(" %c", &a);
                if(a=='L')
                {
                    Xstart = i;
                    Ystart = j;
                }
                Chess[i][j] = a;
        //printf("jf=%d\n", j);
        }
        }

        for(i=0;i<N;i++)
        {
            for(j=0;j<N;j++)
            {
                for(k=1;k<M+1;k++)
                {
                    DP[i][j][k] = -1;
                }
                DP[i][j][0] = 1;
            }
        }

       printf("%ld\n", ways(DP, Chess, Xstart, Ystart, S, N, M));
       T--;
    }
}

long ways(long ***DP, char **Chess, int X, int Y, int s, int N, int M)
{
    if(DP[X][Y][M] !=-1)
    {
    //printf("X=%d Y=%d M=%d Val=%ld\n", X, Y, M, DP[X][Y][M]);
    return DP[X][Y][M];
    }
    else
    {
        long sum1 = 0;


        int S,k;
    sum1 += ways(DP, Chess, X, Y, s, N, M-1);

        for(S=1;S<=s;S++)
    {
        for(k=0;k<=S;k++)
            {
                if(k!=0 && (S-k)!=0)
                {
                    if(X+k<N && Y+(S-k) <N && Chess[X+k][Y+(S-k)] != 'P')
                    {
                        Chess[X+k][Y+(S-k)] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X+k, Y+(S-k), s, N, M-1);
                Chess[X+k][Y+(S-k)] = '.';
                        Chess[X][Y] = 'L';
                    }
                    if(X+k<N && Y-(S-k)>=0 && Chess[X+k][Y-(S-k)] != 'P')
                    {
                        Chess[X+k][Y-(S-k)] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X+k, Y-(S-k), s, N, M-1);
                Chess[X+k][Y-(S-k)] = '.';
                        Chess[X][Y] = 'L';  
                    }
                    if(X-k>=0 && Y+(S-k) <N && Chess[X-k][Y+(S-k)] != 'P')
                    {
                        Chess[X-k][Y+(S-k)] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X-k, Y+(S-k), s, N, M-1);
                Chess[X-k][Y+(S-k)] = '.';
                        Chess[X][Y] = 'L';
                    }
                    if(X-k>=0 && Y-(S-k) >=0 && Chess[X-k][Y-(S-k)] != 'P')
                    {
                        Chess[X-k][Y-(S-k)] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X-k, Y-(S-k), s, N, M-1);
                            Chess[X-k][Y-(S-k)] = '.';
                        Chess[X][Y] = 'L';
                    }


                }
                else if(k==0 && (S-k)!=0)
                {
                    if(Y+(S-k)<N && Chess[X][Y+(S-k)] != 'P')
                    {
                        Chess[X][Y+(S-k)] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X, Y+(S-k), s, N, M-1);
                Chess[X][Y+(S-k)] = '.';
                        Chess[X][Y] = 'L';
                    }
                    if(Y-(S-k)>=0 && Chess[X][Y-(S-k)] != 'P')
                    {
                        Chess[X][Y-(S-k)] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X, Y-(S-k), s, N, M-1);
                Chess[X][Y-(S-k)] = '.';
                        Chess[X][Y] = 'L';
                    }


                }
                else if(k!=0 && (S-k)==0)
                {
                    if(X+k<N && Chess[X+k][Y] != 'P')
                    {
                        Chess[X+k][Y] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X+k, Y, s, N, M-1);
                Chess[X+k][Y] = '.';
                        Chess[X][Y] = 'L';
                    }
                    if(X-k>=0 && Chess[X-k][Y] != 'P')
                    {
                        Chess[X-k][Y] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X-k, Y, s, N, M-1);
                Chess[X-k][Y] = '.';
                        Chess[X][Y] = 'L';
                    }


                }
            }
    }
    //printf("X=%d Y=%d M=%d Val=%ld\n", X, Y, M, sum);
    DP[X][Y][M] = sum1;
        return sum1;
    }   
}
Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ Please don't just post code. Instead, explain the problem (assume the link breaks tomorrow!) and your solution on a higher level. $\endgroup$
    – Juho
    Commented Oct 19, 2012 at 16:31
  • $\begingroup$ Sorry dude, I'm new to stackexchage. $\endgroup$
    – Neeraj Kumar Singh
    Commented Oct 19, 2012 at 16:33
  • 1
    $\begingroup$ (Thank you for adding the ways function - but it would still help us immensely if you explained what you were trying to do in your code!) $\endgroup$
    – Steven Stadnicki
    Commented Oct 19, 2012 at 16:45
  • $\begingroup$ DP[X][Y][M] means 'number of ways in which the S-leaper can move M steps'. For calculating the number of ways in which a S-leaper can move, I'm generating all (x,y) pairs such that x+y<=S. Generating all such pairs itself takes O(N^2). $\endgroup$
    – Neeraj Kumar Singh
    Commented Oct 19, 2012 at 16:53
  • 2
    $\begingroup$ That's a large piece of code, and this is not a programming site. This is definitely the right site to help you with the algorithm, but please meet us part of the way and explain your current solution with English word or ideally readable pseudocode. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Oct 19, 2012 at 18:35

1 Answer 1

Reset to default
5
$\begingroup$

A big hint, since this is 'homework' of a sort: this (obviously?) isn't actually anything resembling a chess problem; instead, it's a graph theory problem in disguise. Consider the graph with $n^2-P$ nodes, one for each cell of the board, and an edge between two nodes if they're a leaper-distance away; then the question is asking for the number of paths of length $M$ on this graph starting from a given point. Now, think about a representation that uses an $n\times n$ array representing the number of paths (of a specific length) from the starting point to the given point. Because the degree of the graph is small (there are roughly $2S^2$ individual moves from any given point), a single iteration (going from the length-$b$ paths to the length-$(b+1)$ paths) should take $O(n^2S^2)$ time and the full algorithm should run in time $O(n^2S^2M)$.

Note that the current algorithm as given by the code is much worse than this: each call to the ways() function is a recursive call, meaning that some values are being recomputed many, many times; its running time is, at first glance, roughly $O(S^{2M})$ (since a call to ways($M$) makes $S^2$ calls to ways($M-1$) and thus the running time $w(M) = S^2\cdot w(M-1)$). Replacing that with an iterative approach where one loops $m$ from $1\ldots M$ and stores the number of paths of length $m$ to each cell, then uses the previous iteration's results to find all the paths of length $m+1$, should make a huge difference.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Correct me if I got this wrong. Use DFS on the graph till depth M. This won't be exactly DFS. We can revisit a node until we reach depth M. I can use DP and store (node, depth) which is number of paths of length depth. Need some clarification about these: a) Calculating all the node which are within leaper distance S will be O(N^2) in worst case. So doing that for all the nodes will be O(N^4) b) How is the degree of a node at most 8? $\endgroup$
    – Neeraj Kumar Singh
    Commented Oct 19, 2012 at 17:22
  • $\begingroup$ DFS isn't the most efficient way to do it in this case - while it's good at finding paths, it's lousy at counting paths. Calculating the nodes that are within distance $S$ isn't $O(N^2)$, it's $O(S^2)$ - which, yes, could be $O(N^2)$ if $S$ is large, but should be tracked independently of $N$. $\endgroup$
    – Steven Stadnicki
    Commented Oct 19, 2012 at 17:48
  • $\begingroup$ As for b), that's a straight-up error on my part; I'm used to the traditional definition of a leaper in fairy chess as a piece which moves specific distances (e.g., the knight is a (1,2) leaper) and missed that this was moving within a 'circle' of length $S$. I've corrected my answer. $\endgroup$
    – Steven Stadnicki
    Commented Oct 19, 2012 at 17:51
  • $\begingroup$ For calculating the number of paths of distance M, DP[node, M] = DP[node1, M-1] + DP[node2, M-1] +....+ DP[nodek, M-1] where node1, node2, ... nodek are adjacent to node. This is O(N^2.S^2.M) which in worst case is O(N^5). N <=200, so O(10^10). This is no different than my solution. I'm getting correct answer for small N using my code, but I get TLE for large N. $\endgroup$
    – Neeraj Kumar Singh
    Commented Oct 19, 2012 at 18:25
  • $\begingroup$ While it's accurate to call the algorithm $O(N^5)$, it's also misleading: $S$ is an independent parameter and should be treated as such in the analysis. $\endgroup$
    – Steven Stadnicki
    Commented Oct 19, 2012 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.