825 - Walking on the Safe Side

[10153EN]

I have a question on this problem~

Does the *minimal path* in the problem description means (width+height-1) or an actual minimal path that reaches the goal from the starting position?

Thx

[Picard]

i've solved it generaly (i still think the problem description allow longer minimal pathes), but now i checked the judge's input and found no minimal path longer as width+height-2

[10153EN]

Yes, you are right.

I just found my bug, initialization of variables~ Suit~

[henar2]

What should the output be if there is a underground passage in the north-west corner or in the south-east corner or in both?
I consider output "0" for these three cases.
Thank you.

[cytse]

I don't think there are such cases in the input, otherwise I should get a SIGABRT

Anyway, I think the output should be 0.

[uzioriluzan]

i've solved it generaly (i still think the problem description allow longer minimal pathes), but now i checked the judge's input and found no minimal path longer as width+height-2

Where can you find judge's input? Have u got the input for problem 827 - Buddy Memory Allocator, too?

Thanks a lot!

[cyfra]

Hi!

I have just solved this task. But there is something wrong in the input.

I mean that there are some spaces after the numbers. For pascal users if they use eoln function it may cause many errors...

I wonder if this could be fixed..

Good Luck

[Observer]

Thanks for your note, cyfra. I've got an AC!!

However, I still don't understand what "minimal paths" mean in this qq........................

Also, my algorithm isn't very good. If the width and height are large, my program can't handle it......
(P.S. I made use of Floyd-Warshall's Algorithm...)

Any suggestions? Any help is warmly welcomed.

[route]

what is the maximum of "positive integers" in the input ?
(width and height)

[eloha]

what is the maximum of "positive integers" in the input ?
(width and height)

100 is enough.

[eloha]

However, I still don't understand what "minimal paths" mean in this qq........................

Also, my algorithm isn't very good. If the width and height are large, my program can't handle it......
(P.S. I made use of Floyd-Warshall's Algorithm...)

Any suggestions? Any help is warmly welcomed.

The minimal paths mean the total steps is (W-1)+(N-1).
And I just use easy DP to solve, because for the tatal different path of position p[j] = p[i-1][j] + p[j-1].

[Dmytro Chernysh]

Did you use long arithmetic? It's quite possilbe to get overflow...

[Observer]

However, I still don't understand what "minimal paths" mean in this qq........................

Also, my algorithm isn't very good. If the width and height are large, my program can't handle it......
(P.S. I made use of Floyd-Warshall's Algorithm...)

Any suggestions? Any help is warmly welcomed.

The minimal paths mean the total steps is (W-1)+(N-1).
And I just use easy DP to solve, because for the tatal different path of position p[j] = p[i-1][j] + p[j-1].

Ah yes! You're right!!

Thanks very much! :p

[Dmytro Chernysh]

Can somebody post a few inputs and outputs? I think I have small mistakes like 0 0 ->1 and so on.
Is it nessesary to use long arithmetic?

[Aleksandrs Saveljevs]

Dima, hi.

I think I have an answer to your not a very recent question.

Is it nessesary to use long arithmetic?

Nope.

Can somebody post a few inputs and outputs?

Here you are:

Code: Select all

8

1 1
1

1 8
1

1 8
1 4

8 1
1
2
3
4
5
6
7
8

8 1
1
2
3
4 1
5
6
7
8

4 4
1
2
3
4

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

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

Code: Select all

1

1

0

1

0

20

0

233

Anyway, try rewriting your code from scratch. That usually helps.