Dynamic maze problem

[Minimacfox]

I am kind of stuck here. Any help is appreciated.

Exercise:
Write a program that takes a width and a height and dynamically generates a maze with the
given width and height. The maze must always have a valid path through it (how can you ensure
this?) Print the maze to the screen once it’s been generated.

#include <iostream>
using namespace std;

int main(){

int h, w, n, *p_h, *p_w;

cout << "enter height: "; cin >> h;
cout << "enter width: "; cin >> w;

p_h = new(nothrow)int[h];
p_w = new(nothrow)int[w];

if(p_h == 0 || p_w == 0)
cout << endl << "Error: Memory allocation failed." << endl;

else{
    for(n = 0; n < h; n++){
        for(n = 0; n < w; n++){

        }
    }
}

}

[booradley60]

Hey, this looks like an interesting problem! I don't know what your limitations are or how your maze is supposed to look, but I banged out an implementation to see how a first pass at it might look. I'll start you off with a few hints to see if it turns into more code than what you've posted here.

First, I treated my maze like a series of floors in a building. Since presumably you're printing to a console, you'll be building these floors top down instead of bottom up. There are three different types of things in my building, a floor (which I represent with an underscore '_'), a wall (which I represent with a pipe character '|'), and a trapdoor (which I represent with a space ' '). So at any point on any floor, either you have a floor, a wall, or a trapdoor.

So the way I guarantee that there is a solution is, on every floor there is at least one trapdoor. Then, when I go to the next floor, I pick another place for there to be a trapdoor and make sure not to put any walls between the new trapdoor and the one on the floor above it. That way, there is always at least one way to get from the current floor to the next floor, and eventually to the bottom.

[booradley60]

Please enter a valid width (1-80): 50

Please enter a valid height (1-250): 20
|____ ______ ___ __ _ ____||_|__|_|____|_|||_______|
||___|_________|_|||____ _____ _______________  |__|
|_______||__ _  _ _________  _ _____ _ __ ___  ___||
|____| __ _________|_|_|_||____||||__|||||___|__||||
|___|__________ _____ ____ _ _ ______ |___|_|____|_|
|__|___||_|_|_____|___|_||____|_|________    ___ __|
|_||________||__||||_____|_|||_|_|___| ____ _ ____||
|___|__ ________   _ ______ _____________|||__||___|
|__||_|____ _ ___ _|_______|_|____|____||_________||
|||||_|_____||__________  |||_||_|____|||__|______||
|___||__|||___||__|_||__|__ __ _ __ ______|__|___|||
||_||____|___||______|__________||____ ____  ____ _|
||_____|_|_|____|___||_|||_____ __  ____ _ _______||
|__|___|_|__||____|_____|__|_|__ _   _____ _ ______|
|_______|___|||_|||__||_||_|__|________|___  |____||
|_ _______ ________ _ __ ____  _____ ____________|_|
|__________ __ _  _______ ___ ____ _____ |___||_|__|
|__|_______|______|_|__|__|__|||____||_|_ __  _ _|_|
|_____|__ __  ___ __ _______________   ___ _____|__|
||__| _  ____||_|__||_|__|____|____|||___||____||__|

Here's some sample output to give you an idea of what I mean. The maze starts at the top and goes to the bottom.

[greenleaf800073]

I got the field, you dig the path:

(I'll work on it):

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

void Display(int height,int width)
{
    for(int i = 0;i < height;i++)
    {
        for(int i2 = 0;i2 < width;i2++)
        {
            cout << '\xB2';
        }
        cout << endl;
    }
}

int main(int nNumberofArgs,char* pszArgs[])
{
    int height,width;

    cout << "Enter height and then width to make box" << endl;
    cout << "Each 'square' is: " << '\xB2' << endl;
    cout << "Height: ";
    cin >> height;
    cout << "Width: ";
    cin >> width;

    Display(height,width);
    system("PAUSE");
    return 0;
}