## 825 - Walking on the Safe Side

Moderator: Board moderators

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

### 825 ..... WA

I got WA again.....

#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;
Last edited by Wei-Ming Chen on Tue Jan 03, 2006 7:12 am, edited 1 time in total.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
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
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
Yeah, my output is 70.
I don't know what is wrong.....

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
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
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
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)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

### 825 (walking in safe side) WA and severe heart attack

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.
Last edited by Shuvra(CSE-BUET) on Sat Aug 12, 2006 7:18 pm, edited 1 time in total.
Life is a challenge.

smile2ka10
New poster
Posts: 13
Joined: Wed Oct 26, 2005 10:14 pm
Location: Iran
Contact:

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
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
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
New poster
Posts: 23
Joined: Thu Mar 30, 2006 5:42 pm
Location: Brazil
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); }
}``````
Regards,
[]'s
Andre

stimim
New poster
Posts: 1
Joined: Mon Sep 24, 2007 4:55 pm

### I have problem!!!

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
New poster
Posts: 8
Joined: Mon Jan 15, 2007 6:53 am
daveon wrote: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] ?
_______________________________________
http://acm.uva.es/problemset/usersnew.php?user=6114

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

### Re: 825 - Walking on the Safe Side

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!
fahim
#include <smile.h>

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### Re: 825 - Walking on the Safe Side

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
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### 825 - Walking on the Safe Side

CUT AFTER ACCC...............
• IMPOSSIBLE MEANS I M POSSIBLE
Last edited by saiful_sust on Fri Feb 05, 2010 9:35 pm, edited 1 time in total.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### 825 - Walking on the Safe Side

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