825 - Walking on the Safe Side

[Wei-Ming Chen]

I got WA again.....
Please help me. Thanks.

#include <stdio.h>
bool a[101][101];
int b[101][101];
int main()
{
int c,d,e,f,h,i,j;
char g;
scanf("%d",&c);
for(d=1;d<=c;d++)
{
scanf("%d %d",&e,&f);
for(h=1;h<=e;h++)
{
for(i=1;i<=f;i++)
{
a[h][i]=0;
}
}
for(h=1;h<=100;h++)
{
b[0][h]=0;
b[h][0]=0;
}
for(h=1;h<=e;h++)
{
scanf("%d%c",&i,&g);
if(g=='\n')
{
continue;
}
for(;;)
{
scanf("%d%c",&i,&g);
a[h][i]=1;
if(g=='\n')
{
break;
}
}
}
b[1][1]=1;

[daveon]

Hi,

INPUT:

Code: Select all

1

10 9
1 1 3 5 7 9
2 
3 1 3 5 7 9
4 
5 1 3 5 7 9
6 
7 1 3 5 7 9
8 
9 1 3 5 7 9
10

The output should be 70.

[Wei-Ming Chen]

Yeah, my output is 70.
I don't know what is wrong.....

[daveon]

Hi Wei-Ming,

Sorry, there was nothing wrong with your algorithm, it is correct.
The problem lies in your input. Here are the corrections to your code that I have made to get it AC.

Code: Select all

#include <stdio.h>
#include <string.h>

int a[1010][1010];
int b[1010][1010];
char line[1000];
char *pch;

int main()
{

int c,d,e,f,h,i,j;
char g;




gets(line);
sscanf(line,"%d",&c);
for(d=1;d<=c;d++)
{
gets(line);
gets(line);
sscanf(line,"%d %d",&e,&f);
for(h=1;h<=e;h++)
{
for(i=1;i<=f;i++)
{
a[h][i]=0;
}
}
for(h=1;h<=100;h++)
{
b[0][h]=0;
b[h][0]=0;
}





for(h=1;h<=e;h++)
{
    gets(line);
    pch=strtok(line," ");
    pch=strtok(NULL," ");
    while(pch!=NULL)
    {
    sscanf(pch,"%d",&i);
    a[h][i]=1;
    pch=strtok(NULL," ");
    }
}





b[1][1]=1;
...
...
...

If you are still getting WA, then I'll send you the corrected code.
Have fun.

[Wei-Ming Chen]

To Daveon: Thanks very much, now I got AC.
The reason that I got WA maybe is there are some spaces after the input.

[Shuvra(CSE-BUET)]

I read all the previous posts but failed to find out the reason of WA. I used dp , tried best to take input properly , and checked all the inputs posted previously.
Now i have no way , but to post my code here. Help me pleeeease .

................................................................................................
code deleted after AC.
Thanks to smile2ka10.

Friends , be careful to take input. I used isspace() , getc() ,ungetc() to get rid of space , tab etc .These are very smart to take complex input.

[smile2ka10]

There are two points about your code:

First, you set p[1][1] after reading input to 1 which is supposed to mean that there is one way to cell (1,1) but it is possible that this cell is blocked so that the answer would be zero paths to cell (r,c).

Second, there is an error in the reading inputs where you want to read the blocked cells, I suggest you to use sstream class and istringstream in order to read them.

After considering these two issues I got your code AC!.

[Donotalo]

i tried every sample input in previous posts and ended up with WA, though for those inputs my program correctly generates the output.

i assumed that if the intersection (1, 1) or (w, n) is blocked, the answer is 0. is there anything wrong? can anyone give me some critical sample input and output?

[ferrizzi]

My solution to this problem run in 0.000 s and I didn't use DP. I just use a matrix to represent the streets and traverse it recursevely, counting a way everytime that it reaches the extreme point.

Code: Select all

int ans=0;
int p[MAX][MAX];

void coutWays(int x, int y){  
    //if it reaches the station
    if(x==l && y==c){ ans++; return; }

    //right
    if(p[x][y+1]==0){ countWays(x, y+1); }    
    
    //down
    if(p[x+1][y]==0){ countWays(x+1, y); }
}

[stimim]

Code: Select all

#include<iostream>
#define UNSAFE -1

using namespace std;

long long map[101][101];
int i,j,I,J,k; //I=>>W J=>>N
char line[1000],*pch;

int main(){
    int N;
    gets(line);
    sscanf(line,"%d",&N);
    while(N--){
        
        gets(line);
        gets(line);
        sscanf(line,"%d %d",&I,&J);
        
        for(i=0;i<=I;i++)
            for(j=0;j<=J;j++)
                map[i][j]=0;
        
        for(i=1;i<=I;i++){
            gets(line);
            pch=strtok(line," \t");
            sscanf(pch,"%d",&k);
            pch=strtok(NULL," \t");
            while(pch!=NULL){
                sscanf(pch,"%d",&j);
                map[k][j] = UNSAFE;
                pch=strtok(NULL," \t");
            }
        }
        map[1][1]=1;
                
        for(i=1;i<=I;i++){
            for(j=1;j<=J;j++){
                if(map[i][j]==UNSAFE)
                    map[i][j]=0;
                else if(map[i][j]==0)
                    map[i][j]=map[i-1][j] + map[i][j-1];
            }
        }
        cout << map[I][J] << endl << endl;
    }

    return 0;
}

That's my code.
I've read many post about 825, I've tried considering if the west-north corner and east-south corner would be unsafe. But still WA.
And I've tried to add some space or Tab in input, but doesn't cause any problem on my computer.
Is there anything wrong??

[Rupak]

Hi,

INPUT:

Code: Select all

1

10 9
1 1 3 5 7 9
2 
3 1 3 5 7 9
4 
5 1 3 5 7 9
6 
7 1 3 5 7 9
8 
9 1 3 5 7 9
10

The output should be 70.

in that case mat[1][1] is forbidden. Is it possible to reach mat[W][N] ?

[smilitude]

my AC code prints 0 for that case.
i got a lots of WA for not using long long. int overflows.
and that input made me nuts for a while!

[stcheung]

This problem is very lenient, no need for fancy algorithm. My simple Java program (using recursion) got AC after running 0.080. Also note that because of the minimal path requirement, you only need to move either down or right at each step.

[saiful_sust]

CUT AFTER ACCC...............

• IMPOSSIBLE MEANS I M POSSIBLE

[saiful_sust]

Hi Shamim
Ur algorithm is Right..
Just a small error i found in ur code...
" The outputs of two consecutive cases will be separated by a blank line."
That means in last line there will be no new line But ur code give an extra new line

Correct it and

One more thing After ACC PLZ remove ur code....

• IMPOSSIBLE MEANS I M POSSIBLE