926 - Walking Around Wisely

[mahade hasan]

getting TLE ...
plz help me with some idea!!

Code: Select all

#include<stdio.h>
#include<string.h>
#include<ctype.h>
int Status[100][100];//Value[100][100];
int Ex,Ey,N,M;
double Ans,Value[100][100];;
double Cal(int I,int K){
    if(I==Ex && K==Ey)return 1;
    if(Value[I][K]==0){
        //printf("I=%d K=%d\n",I,K);
        if(K+1<=N&&Status[I][K]!=3&&Status[I][K+1]!=1){
           Value[I][K]+=Cal(I,K+1);
        }
        if(I+1<=N&&Status[I][K]!=2&&Status[I+1][K]!=4){
           Value[I][K]+=Cal(I+1,K);
        }
    }
    return Value[I][K];
}
int main()
{
    int I,K,L,Tcase,P,Sx,Sy,A,B;
    char C;
    
    scanf("%d",&Tcase);
    for(I=0;I<Tcase;I++){
        scanf("%d",&N);
        for(K=1;K<=N;K++)
          for(L=1;L<=N;L++)
             Status[K][L]=Value[K][L]=0;
             
        scanf("%d %d",&Sx,&Sy);
        scanf("%d %d",&Ex,&Ey);
        scanf("%d",&P);
        while(P--){
            scanf("%d %d %c",&A,&B,&C);
            if(C=='W') Status[A][B]=4;
            else if(C=='S') Status[A][B]=1;
            else if(C=='E') Status[A][B]=2;
            else if(C=='N') Status[A][B]=3;
        }
        printf("%0.0lf\n",Cal(Sx,Sy));
    }
    return 0;
} 

[/color]

[brianfry713]

Try input:

Code: Select all

1
30
2 1
1 1
0

[mahade hasan]

now i m deal with Wrong Answer

Code: Select all

#include<stdio.h>
#include<string.h>
#include<ctype.h>
int Status[100][100];//Value[100][100];
int Ex,Ey,N,M;
double Ans,Value[100][100];
bool Trak[100][100];
double Cal(int I,int K){
    if(I==Ex && K==Ey)return 1;
    if(Value[I][K]==0&&!Trak[I][K]){
        Trak[I][K]=true;
        //printf("I=%d K=%d\n",I,K);getchar();
        if(K+1<=N&&Status[I][K]!=3&&Status[I][K+1]!=1){
            //printf("1\n");
           Value[I][K]+=Cal(I,K+1);
        }
        if(I+1<=N&&Status[I][K]!=2&&Status[I+1][K]!=4){
           //printf("2\n");
           Value[I][K]+=Cal(I+1,K);
        }
    }
    //printf("yes\n");
    return Value[I][K];
}
int main()
{
    int I,K,L,Tcase,P,Sx,Sy,A,B;
    char C;
    
    scanf("%d",&Tcase);
    for(I=0;I<Tcase;I++){
        scanf("%d",&N);
        for(K=1;K<=N;K++)
          for(L=1;L<=N;L++)
             Status[K][L]=Trak[K][L]=Value[K][L]=0;
             
        scanf("%d %d",&Sx,&Sy);
        scanf("%d %d",&Ex,&Ey);
        scanf("%d",&P);
        while(P--){
            scanf("%d %d %c",&A,&B,&C);
            if(C=='W') Status[A][B]=4;
            else if(C=='S') Status[A][B]=1;
            else if(C=='E') Status[A][B]=2;
            else if(C=='N') Status[A][B]=3;
        }
        printf("%0.0lf\n",Cal(Sx,Sy));
    }
    return 0;
} 

[/color]

[brianfry713]

Don't use floating point on this problem.

[mahade hasan]

Don't use floating point on this problem.

can u help me with some input!

[predicate]

some random test cases to help debug:
input:

Code: Select all

10
30
1 1
30 30
83
5 7 W
9 16 N
11 4 S
16 6 S
25 14 W
11 6 E
10 25 W
7 3 S
11 9 S
24 2 N
9 11 E
20 16 W
15 10 E
15 16 N
8 14 W
23 25 S
25 23 E
25 15 W
13 8 W
16 16 S
8 7 S
14 14 W
14 25 E
20 21 E
11 7 W
25 15 W
20 2 E
19 2 E
14 21 S
21 14 W
24 13 N
17 16 S
5 4 S
22 9 W
5 2 N
6 5 N
21 11 W
4 12 N
8 18 E
23 21 N
8 24 S
25 13 S
13 22 E
12 2 W
3 11 N
25 25 E
11 4 E
4 10 S
25 5 S
25 20 E
12 5 E
24 14 W
7 12 W
9 18 S
20 21 N
11 9 E
15 8 E
20 20 W
12 15 N
19 12 S
10 10 N
4 3 S
5 25 E
17 23 W
2 23 W
22 4 S
3 24 N
16 20 W
4 5 S
6 3 E
18 20 E
7 23 E
24 16 W
17 19 N
3 12 E
5 2 W
17 10 S
3 18 E
12 23 E
18 2 N
18 19 E
9 13 E
13 9 E
30
1 1
30 30
44
14 13 E
7 17 W
13 6 W
5 14 E
25 11 N
24 10 N
4 3 W
25 18 W
18 10 W
10 11 N
5 25 N
14 16 S
3 14 E
7 6 E
12 21 N
21 7 E
8 15 W
10 15 W
5 4 E
23 8 S
2 20 N
22 12 E
11 4 W
21 22 W
6 14 S
3 13 N
11 24 S
11 7 N
7 19 S
21 13 S
21 10 S
20 15 W
6 8 E
18 18 E
15 18 W
12 19 N
11 18 S
5 18 W
14 12 W
20 19 E
7 18 N
24 12 W
14 2 W
14 11 S
30
1 1
30 30
66
13 9 W
21 11 N
14 17 W
15 13 E
16 12 S
8 8 N
12 19 N
19 14 E
23 23 N
8 5 W
17 7 W
10 10 N
12 14 W
11 8 W
4 8 W
13 20 W
12 2 W
11 20 N
20 9 S
19 22 W
18 6 N
22 6 N
13 16 E
24 17 E
10 2 S
15 6 W
22 17 E
8 3 W
16 18 E
17 13 N
6 17 N
20 19 S
11 23 E
23 24 E
2 13 W
3 10 N
8 8 E
17 15 W
18 14 E
6 22 N
5 6 E
3 6 E
7 3 E
19 17 W
9 13 N
13 10 E
16 19 E
15 24 N
10 8 N
20 2 N
11 16 S
21 25 N
6 13 W
8 17 S
15 20 N
17 6 S
20 8 N
15 20 S
17 8 N
11 13 E
4 12 W
5 8 S
9 6 W
10 9 S
17 15 W
17 15 W
30
1 1
30 30
53
4 12 S
14 15 N
8 25 N
5 10 E
11 19 E
12 7 E
9 23 S
10 11 E
8 5 S
8 15 E
7 10 E
11 5 N
2 8 W
18 9 W
11 2 E
21 25 W
23 13 N
3 13 E
7 15 S
15 14 W
4 14 W
3 24 W
14 8 E
19 20 E
13 13 N
17 22 W
14 5 N
2 10 W
15 21 W
24 19 E
11 25 W
25 15 S
6 19 S
10 16 E
12 4 S
7 2 E
12 24 W
4 20 N
10 4 S
20 12 W
24 7 W
3 2 W
19 14 N
17 11 W
7 23 S
15 17 N
23 5 E
8 5 W
4 13 E
12 11 W
7 6 S
24 15 N
6 4 S
30
1 1
30 30
13
15 15 N
13 15 W
25 10 S
18 25 N
6 18 E
18 7 W
8 20 S
6 6 W
3 8 W
8 7 N
18 17 W
22 24 N
3 12 N
30
1 1
30 30
64
9 12 S
19 17 N
22 13 W
23 18 W
25 3 E
3 9 N
20 2 N
9 5 S
21 12 S
20 19 E
3 18 W
24 6 E
23 17 W
24 18 N
7 20 E
9 2 E
25 23 W
11 25 E
21 12 S
6 7 N
16 9 S
4 24 W
16 7 S
24 20 N
23 6 E
24 12 N
23 17 S
11 16 W
19 11 E
10 4 E
23 8 S
25 20 N
6 2 S
2 17 W
13 24 E
19 9 N
13 3 N
15 5 S
7 15 W
3 13 N
23 25 E
14 3 W
14 6 S
18 6 N
17 8 S
8 15 E
16 14 N
2 24 S
20 12 W
9 8 W
3 6 E
4 20 N
8 11 S
11 8 W
22 18 E
19 19 W
5 18 E
2 17 W
6 6 W
2 13 W
2 5 S
20 8 S
16 18 N
15 16 N
30
1 1
30 30
21
25 24 S
11 24 E
9 10 S
23 19 N
21 19 W
16 3 E
14 25 N
15 17 W
8 21 N
22 13 S
8 18 W
10 4 E
24 8 N
3 19 N
15 7 N
23 21 N
10 17 S
5 20 E
6 22 W
17 3 S
3 23 E
30
1 1
30 30
86
25 10 W
20 6 S
14 3 E
16 3 W
8 13 W
2 16 S
5 24 E
18 13 E
3 10 W
14 6 N
22 25 N
18 24 S
5 13 N
7 17 N
12 8 N
17 19 W
2 15 N
6 14 N
4 25 E
8 4 E
8 24 E
15 20 E
8 22 E
12 5 W
21 5 N
19 22 W
4 13 N
9 2 N
25 5 N
21 14 N
21 20 N
14 19 W
19 19 S
6 16 W
6 8 W
8 2 S
21 10 S
11 23 W
4 19 W
8 7 S
2 22 N
16 8 N
3 3 E
6 13 E
6 13 S
4 9 N
24 8 E
19 5 N
19 18 S
19 9 W
17 5 S
4 3 E
7 13 N
22 13 N
7 12 W
6 4 E
9 18 E
24 25 S
3 11 W
17 9 W
16 3 S
17 24 N
7 3 W
17 22 E
14 19 S
14 9 S
20 3 E
9 20 E
6 25 S
3 20 W
2 7 S
7 4 N
10 22 S
19 15 E
17 24 E
11 20 W
17 19 E
4 20 W
24 8 E
19 12 S
21 15 S
17 19 S
14 8 S
24 24 S
18 18 S
6 3 S
30
1 1
30 30
78
5 13 N
6 15 N
25 24 E
23 13 S
17 23 E
2 12 N
15 19 S
22 20 N
11 3 S
16 24 S
6 18 W
22 19 W
4 25 E
17 10 N
2 18 E
9 24 S
7 16 N
5 20 E
10 25 N
20 17 N
7 22 S
5 3 S
23 3 N
10 11 N
20 2 E
20 5 S
18 20 S
5 9 W
9 17 W
21 10 S
10 9 S
15 3 S
24 12 N
13 8 E
25 24 S
7 10 W
19 24 E
5 4 W
4 13 E
24 20 W
2 22 W
18 11 S
13 19 S
22 8 S
8 9 W
19 20 N
9 18 N
15 7 E
15 15 E
23 21 N
18 21 S
16 15 W
4 3 S
10 24 S
6 3 E
17 10 N
2 6 S
21 2 W
8 25 N
5 14 E
14 5 S
19 4 W
6 23 E
17 20 E
11 5 E
18 13 E
22 20 W
14 8 W
7 8 S
17 19 W
12 4 N
18 6 E
10 20 W
23 24 W
5 23 S
11 20 N
14 10 W
22 6 W
30
1 1
30 30
24
25 23 S
23 18 N
9 22 W
17 17 N
12 11 N
12 7 W
7 14 W
14 5 W
24 18 S
11 18 N
2 10 S
3 13 W
24 9 E
5 14 E
11 10 W
15 10 S
22 17 W
11 11 N
10 24 S
4 12 W
22 5 N
5 22 W
15 4 W
22 12 E

output:

Code: Select all

524163352159486
4567127025267383
850805935788650
3900401334150343
15594085034258247
3027817074384319
15631807699873733
2065101199612301
1274749777923101
13608932962285231