天天看點

自己寫的一個迷宮問題C語言

#include <iostream>
#include <fstream>
#include<stack>

using namespace std;

struct Pos
{
    int x;
    int y;
    int di;
};
void mazePath();
void printMazePath();

#define MAZE_SIZE = 10
定義一個迷宮,0表示通道,1表示牆
int maze[10][10] = 
{
	{0,1,1,1,1,1,1,1,1,1},
	{0,0,0,1,1,0,0,1,0,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,0,0,1},
	{1,0,1,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,0,1},
	{1,0,1,1,1,0,1,1,0,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,0,0}
};
stack <Pos> posStack;
int xe = 9;
int ye = 9;
ofstream ff("me.txt");
int main(void)
{
    Pos pos;
    pos.x = 0;
    pos.y = 0;
    pos.di = 0;
    posStack.push(pos);
    mazePath();
    system("PAUSE");
    return 0;
}

void mazePath()
{
    if(posStack.empty())
    {
        //ff<<"No answer"<<endl;
        return;
    }
    Pos pos = posStack.top();
    if(pos.x==xe && pos.y==ye)
    {
        //ff<<"Over"<<endl;
        printMazePath();
        
        //以下代碼開啟,表示求出所有可能路徑  
        posStack.pop();
        maze[pos.y][pos.x] = 0;
        mazePath();
        
        return;
    }
    
    if(pos.di<4)
    {
        int nextX;
        int nextY;
        switch(pos.di)
        {
        case 0:
             nextX = pos.x+1;
             nextY = pos.y;
             break;
        case 1:
             nextX = pos.x;
             nextY = pos.y+1;
             break;
        case 2:
             nextX = pos.x-1;
             nextY = pos.y;
             break;
        case 3:
             nextX = pos.x;
             nextY = pos.y-1;
             break;
        default:
             break;
        }
        
        if((nextX>=0 && nextX<10) && (nextY>=0 && nextY<10) && (maze[nextY][nextX]==0))
        {
            pos.di += 1;
            posStack.pop();
            posStack.push(pos);
            
            Pos nextPos;
            nextPos.di = 0;
            nextPos.x = nextX;
            nextPos.y = nextY;
            posStack.push(nextPos);
            
            maze[pos.y][pos.x] = -1;
            //ff<<"NextOK"<<" "<<pos.x<<" "<<pos.y<<" "<<pos.di-1<<endl;
            
            
            
            mazePath();
        }
        else
        {
            pos.di += 1;
            posStack.pop();
            posStack.push(pos);
            //ff<<"NextNotOK"<<" "<<pos.x<<" "<<pos.y<<" "<<pos.di<<endl;
            mazePath();
        }
    }
    else
    {
        //該位置不同,從棧頂删除,且mg[][]=0 
        //ff<<"Back"<<" "<<pos.x<<" "<<pos.y<<" "<<pos.di<<endl;
        posStack.pop();
        maze[pos.y][pos.x] = 0;
        mazePath();
    }
    
    
}
void printMazePath()
{
    stack <Pos> backupStack;
    ff<<"Path:"; 
    while(!posStack.empty())
    {
        Pos pos = posStack.top();
        posStack.pop();
        backupStack.push(pos);
    }
    while(!backupStack.empty())
    {
        Pos pos = backupStack.top();
        backupStack.pop();
        posStack.push(pos);
        ff<<"<"<<pos.x<<","<<pos.y<<"> ";
    }
    ff<<endl;
}
           

繼續閱讀