March 30, 2009

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

 


// 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;
}

Today's Visitors: 0 Total Visitors: 23
[Trackback URL]

Post A Comment









Yes No



Please input the magic number:

( Prevent the annoy garbage messages )
( What if you cannot see the numbers? )
Please input the magic number

誰來收藏
Loading ...
unlog_NVPO 0