When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

bradyawn's blog

By bradyawn, history, 6 years 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

| Write comment?
»
6 years 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.

  • »
    »
    6 years 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.

    • »
      »
      »
      6 years 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?

      • »
        »
        »
        »
        6 years 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)

        • »
          »
          »
          »
          »
          6 years 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.