資料結構作業二:老鼠走迷宮(堆疊)

// MAIN.CPP
#include <iostream.h>
#include <stdlib.h>
#include <windows.h>
//////////////////////////////////////
// Global Viriable Declarations Start
//////////////////////////////////////
int *gSP = (int*)malloc(1024);
int *gSPBase = gSP;
int *gSPLimit = (gSP+1024);
int Stack_Empty = 1;
int Stack_Full = 0;
const int ROAD = 0;
const int WALL = 1;
const int NOW = 2;
const int PASS = 3;
//////////////////////////////////////
// Global Viriable Declarations End
//////////////////////////////////////
//////////////////////////////////////
// Function Declaration Start
//////////////////////////////////////
void showArray(void);
int Visit(void);
void PUSH(int x);
int POP(void);
void StorePosition(void);
void RestorePosition(void);
void PrintOutTheShortestPath(void);
//////////////////////////////////////
// Function Declaration End
//////////////////////////////////////
//////////////////////////////////////
// Name : StorePosition
//
// Input : None
//
// Output : None
//////////////////////////////////////
void StorePosition(void)
{
extern i_Position;
extern j_Position;
PUSH(i_Position);
PUSH(j_Position);
}
//////////////////////////////////////
// Name : RestorePosition
//
// Input : void
//
// Output : None
//////////////////////////////////////
void RestorePosition(void)
{
extern i_Position;
extern j_Position;
j_Position = POP();
i_Position = POP();
}
//////////////////////////////////////
// Name : PUSH
//
// Input : int x
//
// Output : None
//////////////////////////////////////
void PUSH(int x)
{
if(Stack_Full)
{
cout << "Stack is Full!!" << endl;
while(1){};
}
else
{
*gSP = x;
if(gSP == gSPLimit)
Stack_Full = 0x01;
gSP++;
Stack_Empty = 0x00;
}
}
//////////////////////////////////////
// Name : POP
//
// Input : None
//
// Output : int x
//////////////////////////////////////
int POP(void)
{
int x;
if(Stack_Empty)
{
cout << "Stack is empty!!" << endl;
while(1){};
} else {
--gSP;
Stack_Full = 0x00;
x = *gSP;
if(gSP == gSPBase)
Stack_Empty = 0x01;
}
return x;
}
//////////////////////////////////////
// Name : Visit
//
// Input : None
//
// Output : int
//////////////////////////////////////
int Visit(void)
{
extern array[20][20];
extern i_Position;
extern j_Position;
array[i_Position][j_Position] = PASS;
showArray();
Sleep(20);
// ↑
if(array[i_Position-1][j_Position] == ROAD)
{
i_Position--;
return 0;
}
// ↗
if(array[i_Position-1][j_Position+1] == ROAD)
{
i_Position--;
j_Position++;
return 0;
}
// →
if(array[i_Position][j_Position+1] == ROAD)
{
j_Position++;
return 0;
}
// ↘
if(array[i_Position+1][j_Position+1] == ROAD)
{
i_Position++;
j_Position++;
return 0;
}
// ↓
if(array[i_Position+1][j_Position] == ROAD)
{
i_Position++;
return 0;
}
// ↙
if(array[i_Position+1][j_Position-1] == ROAD)
{
i_Position++;
j_Position--;
return 0;
}
// ←
if(array[i_Position][j_Position-1] == ROAD)
{
j_Position--;
return 0;
}
// ↖
if(array[i_Position-1][j_Position-1] == ROAD)
{
i_Position--;
j_Position--;
return 0;
}
return 0;
}
//////////////////////////////////////
// Name : showArray
//
// Input : None
//
// Output : None
//////////////////////////////////////
void showArray(void)
{
extern i_Position;
extern j_Position;
extern array[20][20];
int a, b;
system("cls");
PUSH(array[i_Position][j_Position]);
for(a = 0; a < 20; a++)
{
for(b = 0; b < 20; b++)
{
array[i_Position][j_Position] = NOW;
if(a == 1 && b == 1 && (array[a][b] == ROAD || array[a][b] == PASS))
cout << "☆";
if(a == 16 && b == 12 && array[a][b] == ROAD)
cout << "★";
if(array[a][b] == WALL)
cout << "■";
if((array[a][b] == ROAD || array[a][b] == PASS) &&
(!(a == 16 && b == 12 && array[a][b] == ROAD)) &&
(!(a == 1 && b == 1 && (array[a][b] == ROAD || array[a][b] == PASS)))
)
cout << " ";
if(array[a][b] == NOW)
cout << "囧";
if(b==19)
cout << endl;
}
}
array[i_Position][j_Position] = POP();
cout << "Current Position : [" << i_Position << "][" << j_Position << "]" << endl;
}
//////////////////////////////////////
// Name : PrintOutTheShortestPath
//
// Input : None
//
// Output : None
//////////////////////////////////////
void PrintOutTheShortestPath(void)
{
extern i_Position;
extern j_Position;
int *pp;
int x = 1;
cout << "Print out the shortest path." << endl;
pp = gSPBase;
while(gSPBase != gSP)
{
if(x == 1)
{
cout << "<START> ";
x++;
}
i_Position = *gSPBase;
gSPBase++;
j_Position = *gSPBase;
gSPBase++;
cout << "[" << i_Position << "][" << j_Position << "] -> ";
if(!(x % 5))
cout << endl;
x++;
}
cout << "<END>" << endl;
gSP = gSPBase = pp;
}
//////////////////////////////////////////
// Input.h
int Start_i = 1;
int Start_j = 1;
int i_Position = Start_i;
int j_Position = Start_j;
int Goal_i = 16;
int Goal_j = 12;
int array[20][20] = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1},
{1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1},
{1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};
//////////////////////////////////////////
// MyFunction.h
#include <iostream.h>
#include <stdlib.h>
#include <windows.h>
//////////////////////////////////////
// Global Viriable Declarations Start
//////////////////////////////////////
int *gSP = (int*)malloc(1024);
int *gSPBase = gSP;
int *gSPLimit = (gSP+1024);
int Stack_Empty = 1;
int Stack_Full = 0;
const int ROAD = 0;
const int WALL = 1;
const int NOW = 2;
const int PASS = 3;
//////////////////////////////////////
// Global Viriable Declarations End
//////////////////////////////////////
//////////////////////////////////////
// Function Declaration Start
//////////////////////////////////////
void showArray(void);
int Visit(void);
void PUSH(int x);
int POP(void);
void StorePosition(void);
void RestorePosition(void);
void PrintOutTheShortestPath(void);
//////////////////////////////////////
// Function Declaration End
//////////////////////////////////////
//////////////////////////////////////
// Name : StorePosition
//
// Input : None
//
// Output : None
//////////////////////////////////////
void StorePosition(void)
{
extern i_Position;
extern j_Position;
PUSH(i_Position);
PUSH(j_Position);
}
//////////////////////////////////////
// Name : RestorePosition
//
// Input : void
//
// Output : None
//////////////////////////////////////
void RestorePosition(void)
{
extern i_Position;
extern j_Position;
j_Position = POP();
i_Position = POP();
}
//////////////////////////////////////
// Name : PUSH
//
// Input : int x
//
// Output : None
//////////////////////////////////////
void PUSH(int x)
{
if(Stack_Full)
{
cout << "Stack is Full!!" << endl;
while(1){};
}
else
{
*gSP = x;
if(gSP == gSPLimit)
Stack_Full = 0x01;
gSP++;
Stack_Empty = 0x00;
}
}
//////////////////////////////////////
// Name : POP
//
// Input : None
//
// Output : int x
//////////////////////////////////////
int POP(void)
{
int x;
if(Stack_Empty)
{
cout << "Stack is empty!!" << endl;
while(1){};
} else {
--gSP;
Stack_Full = 0x00;
x = *gSP;
if(gSP == gSPBase)
Stack_Empty = 0x01;
}
return x;
}
//////////////////////////////////////
// Name : Visit
//
// Input : None
//
// Output : int
//////////////////////////////////////
int Visit(void)
{
extern array[20][20];
extern i_Position;
extern j_Position;
array[i_Position][j_Position] = PASS;
showArray();
Sleep(20);
// ↑
if(array[i_Position-1][j_Position] == ROAD)
{
i_Position--;
return 0;
}
// ↗
if(array[i_Position-1][j_Position+1] == ROAD)
{
i_Position--;
j_Position++;
return 0;
}
// →
if(array[i_Position][j_Position+1] == ROAD)
{
j_Position++;
return 0;
}
// ↘
if(array[i_Position+1][j_Position+1] == ROAD)
{
i_Position++;
j_Position++;
return 0;
}
// ↓
if(array[i_Position+1][j_Position] == ROAD)
{
i_Position++;
return 0;
}
// ↙
if(array[i_Position+1][j_Position-1] == ROAD)
{
i_Position++;
j_Position--;
return 0;
}
// ←
if(array[i_Position][j_Position-1] == ROAD)
{
j_Position--;
return 0;
}
// ↖
if(array[i_Position-1][j_Position-1] == ROAD)
{
i_Position--;
j_Position--;
return 0;
}
return 0;
}
//////////////////////////////////////
// Name : showArray
//
// Input : None
//
// Output : None
//////////////////////////////////////
void showArray(void)
{
extern i_Position;
extern j_Position;
extern array[20][20];
int a, b;
system("cls");
PUSH(array[i_Position][j_Position]);
for(a = 0; a < 20; a++)
{
for(b = 0; b < 20; b++)
{
array[i_Position][j_Position] = NOW;
if(a == 1 && b == 1 && (array[a][b] == ROAD || array[a][b] == PASS))
cout << "☆";
if(a == 16 && b == 12 && array[a][b] == ROAD)
cout << "★";
if(array[a][b] == WALL)
cout << "■";
if((array[a][b] == ROAD || array[a][b] == PASS) &&
(!(a == 16 && b == 12 && array[a][b] == ROAD)) &&
(!(a == 1 && b == 1 && (array[a][b] == ROAD || array[a][b] == PASS)))
)
cout << " ";
if(array[a][b] == NOW)
cout << "囧";
if(b==19)
cout << endl;
}
}
array[i_Position][j_Position] = POP();
cout << "Current Position : [" << i_Position << "][" << j_Position << "]" << endl;
}
//////////////////////////////////////
// Name : PrintOutTheShortestPath
//
// Input : None
//
// Output : None
//////////////////////////////////////
void PrintOutTheShortestPath(void)
{
extern i_Position;
extern j_Position;
int *pp;
int x = 1;
cout << "Print out the shortest path." << endl;
pp = gSPBase;
while(gSPBase != gSP)
{
if(x == 1)
{
cout << "<START> ";
x++;
}
i_Position = *gSPBase;
gSPBase++;
j_Position = *gSPBase;
gSPBase++;
cout << "[" << i_Position << "][" << j_Position << "] -> ";
if(!(x % 5))
cout << endl;
x++;
}
cout << "<END>" << endl;
gSP = gSPBase = pp;
}
Previous in This Category: 資料結構作業三:Linking List, Create、Insert、Delete and Search(Node, Data, Number and Final). Next in This Category: 資料結構作業三:Linking List, Create、Insert、Delete and Search(Node, Data, Number and Final).

