10818 - Dora Trip

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

10818 - Dora Trip

Post by little joey » Tue Feb 15, 2005 10:31 am

The first line of each case contains two integers r and c (1 <= r, c <= 20), which are the number of rows and columns of the map respectively. The next r lines, each with c characters, give the map itself.
But the input contains lines that have less than c characters. Got many WAs debugging a correct program because of that. :evil:

EDIT: This remark was false. Read on to know why.
Last edited by little joey on Tue Feb 15, 2005 2:57 pm, edited 3 times in total.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Feb 15, 2005 10:37 am

Oh is that so? I'm pretty sure that the input file that I send to the judge is alright. (I could send that to you if you wish.) Maybe you should ask the system admin about that? :-?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Feb 15, 2005 10:49 am

This little program ends in SIGABRT on the judges' input:

Code: Select all

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

int main(){
   int rows,cols;
   int r;
   char line[128];
   
   while(1){
      scanf("%d%d\n",&rows,&cols);
      if(!(rows&&cols)) break;
      for(r=0;r<rows;r++){
         fgets(line,sizeof(line),stdin);
         assert(strlen(line)>=cols);
         }
      }
   return 0;
   }

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Feb 15, 2005 10:50 am

But this program doesn't get TLE. It terminates at 0.00.000:

Code: Select all

var st : string;
    i, r, c : longint;
begin
  readln(r, c);
  while (r<>0) or (c<>0) do begin
    for i := 1 to r do begin
      readln(st);
      while length(st) < c do write;
    end;
    readln(r, c);    
  end;
end.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Feb 15, 2005 11:12 am

Well, that's realy strange.
I have to go now, but I'll think about it.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Feb 15, 2005 11:15 am

Okay... Btw, could you add a question mark (?) at the end of the title of this topic? After all, we're still not sure whether the input is bad or not.. :P
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Feb 15, 2005 2:54 pm

Thanks Observer for sending me the input. It contained no bad input, as I previously assumed, but I just discovered a very funny 'feature' in C.

If you want to read two numbers and proceed to the next line (like readln(r,c) in Pascal) you can use scanf("%d%d\n",&r,&c), but then it will also read all space chars that follow the newline.

So for a case like this

Code: Select all

5 5
  ###
###S#
#   #
#***#
#####
scanf("%d%d\n",&r,&c) will also 'eat' the two spaces on the next line! In that case the maze would be read as if it were

Code: Select all

###
###S#
#   #
#***#
#####
It may be my laymanship in C (I switched from Pascal to C last year), but who would have expected that behaviour?

So sorry for the unjust accusation. I didn't know better, but learned now...

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Tue Feb 15, 2005 6:12 pm

I also follow the following two rules while reading with C

a) Do not use '\n' in scanf()
b) Do not use scanf() and gets() together. If use of gets() is urgent then use gets() always and sscanf() to read input from the string read by gets().

For this type of mistake I suffered with a problem in volume IV, probably "Graph connectivity" and for another easy problem in volume II probably "Puzzle"

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Feb 15, 2005 6:44 pm

Use gets and sscanf, Manzoor is right. Though if you're careful, and you know what you're doing, you can use scanf and gets.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Feb 15, 2005 6:52 pm

You could also use:
char skip,s[1000];
scanf("%d %d%[^\n]%c",&r,&c,s,&skip);
that should first read everything up to the \n into s and the \n into skip.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Feb 15, 2005 8:00 pm

Thank you guys for your advises.
I think reading input is one of the most hairy parts of programming (especialy when you suspect errors). Mostly I find myself writing special parsers based on getchar() just to avoid difficulties, but at contest time that is too expensive. I have yet enough to learn...
One question to Adrian: will scanf("%[^\n]",s) read _all_ characters upto the newline, including spaces, tabs and lower asciis?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Feb 15, 2005 9:02 pm

Yes, since the %[^\n] literally means "any character not \n"..

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

10818 Dora Trip WAing..

Post by liulike » Wed Feb 16, 2005 8:58 am

I need some testdata for 10818 :-?
Here is my I/O, are they correct?

Thanks!

Input:

Code: Select all

7 7
#######
#*   *#
#  X X#
#  S *#
#*   *#
#*****#
#######
6 6
######
#*  *#
#X  X#
#   *#
#S  *#
######
6 6
######
#S  *#
#  XX#
#   *#
#*  *#
######
5 5
#####
#S X#
# *X#
#*#*#
#####
Output:

Code: Select all

EESSWWWWNNNNEEEEWSSW
EEENWNNEWWWESSSW
EEEWWSSEESWWWNNN
ESWSNN
Last edited by liulike on Wed Feb 16, 2005 9:46 am, edited 1 time in total.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Re: 10818 Dora Trip WAing..

Post by Observer » Wed Feb 16, 2005 9:10 am

Not quite... We ask for the lexicographically smallest shortest path, thus your first two outputs are not correct.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post by liulike » Wed Feb 16, 2005 9:48 am

Sorry for that wrong output.
I has modified it.

But I still got WA .

Post Reply

Return to “Volume 108 (10800-10899)”