bradyawn's blog

By bradyawn, history, 4 weeks ago, In English,

I'm writing code that takes in a "maze" and runs bfs. I have already solved it for small test cases, but the code for taking in input fails on large test cases.

Given W (1 <= W <= 38), the width of the maze; H (1 <= H <= 100), the height of the maze; 2*H+1 lines with width 2*W+1 characters that represent the maze in a format like this:

Example of a 5X3 Maze
Example of a 25x25 Maze - Code Fails on This Input
Full Problem Statement

Issue: The loop that takes in the maze stops when i = 19 for the 25x25 maze.

EDIT: Clarification — "taken" will never be printed on the failing test case.

Any ideas what's causing this?

 
 
 
 
  • Vote: I like it  
  • -16
  • Vote: I do not like it  

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by bradyawn (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by bradyawn (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Also I have the macro #define inf cin, so the inf there is just cin.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The suspense is killing me... Anybody got any idea?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are you saying that not all the input goes into the vector?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Kind of. The program just "stops running" once I take in the 19th line. On the judge I submit in (USACO training pages) I get an MLE but I suspect the problem is something else (e.g undefined behavior as yeputons has mentioned)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please provide a Minimal, Complete, and Verifiable example. My assumption is that your program has undefined behavior somewhere later in the program and so it does not flush output buffer, therefore you do not see the taken line. Try removing everything except for the reading and see if the problem persists. If it does, remove more stuff.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, I commented out the bfs code/logic stuffs when I ran it. I will update it with a better example. EDIT: I updated it with a better example.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your code works fine on Ideone. Do you have an environment where that exact code does not work?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I use xCode 9 with C++11. It seems that it was xCode's fault it was not working, as the input works on the online judge.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        As for the problem, I am getting 'std::bad_alloc' which I thought was an input issue but it seems I am allocating too much memory. (Not sure how I am taking > 16MB though)

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It may be the case that you try to pass something like -1 to an allocation function which converts that to an unsigned type which results in several billions. Try printing w and h in the very beginning to ensure that your reading is ok.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ah, yes it was an infinite loop. Thanks for the pointer, I was able to fix/solve it.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by bradyawn (previous revision, new revision, compare).