COMP 2710 Lab 3

maze.cpp

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <fstream>
#include <sstream>
#include <map>
#include <queue>
#include <vector>
#include <utility>

class Node
{
 public:
  Node()
      : name_("")
      , numberUsed_(0)
      , previous_(0)
      , marked_(0)
  { }
  Node(const std::string &name)
      : name_(name)
      , numberUsed_(0)
      , previous_(0)
      , marked_(0)
  { }

  void setNodeName(const std::string &name)
  { name_ = name; }
  const std::string getNodeName() const
  { return name_; }

  void attachNewNode(Node *nd, int ind)
  { attachedNode_[ind] = nd; };
  Node *getAttachedNode(int ind)
  { return attachedNode_[ind]; };

  int getNumberUsed() const
  { return numberUsed_; }
  int setNumberUsed(int n)
  { return (numberUsed_ = n); }

  void setPrevious(Node *prev)
  { previous_ = prev; }
  Node *getPrevious()
  { return previous_; }

  int setMarked()
  { return (marked_ = 1); }
  bool isMarked()
  { return (1 == marked_); }

 private:
  std::string name_;
  Node *attachedNode_[4];
  int numberUsed_;
  Node *previous_;
  int marked_;
};

class Maze
{
 public:
  ~Maze() {
    for (std::map<std::string, Node *>::iterator it = nodes_.begin();
         it != nodes_.end(); ++it)
      delete it->second;
    nodes_.clear();
  }

  void add_edge(const std::string &a, const std::string &b) {
    Node *na, *nb;

    if (nodes_.find(a) == nodes_.end())
      na = nodes_[a] = new Node(a);
    else na = nodes_[a];
    if (nodes_.find(b) == nodes_.end())
      nb = nodes_[b] = new Node(b);
    else nb = nodes_[b];

    int n = na->getNumberUsed();
    for (int i = 0; i < n; ++i) {
      Node *t = na->getAttachedNode(i);
      if (!b.compare(t->getNodeName()))
        return;
    }

    na->attachNewNode(nb, na->getNumberUsed());
    na->setNumberUsed(na->getNumberUsed() + 1);

    nb->attachNewNode(na, nb->getNumberUsed());
    nb->setNumberUsed(nb->getNumberUsed() + 1);
  }

  std::vector<std::string>
  solve(const std::string &a, const std::string &b) {
    std::vector<std::string> ret;

    if (nodes_.find(a) == nodes_.end() ||
        nodes_.find(b) == nodes_.end())
      return ret;

    std::queue<std::string> q;
    q.push(a);

    while (q.size()) {
      std::string name = q.front(); q.pop();
      printf(" %s", name.c_str());

      Node *cur = nodes_[name];
      cur->setMarked();

      if (!name.compare(b)) {
        for (Node *p = cur; p != 0; p = p->getPrevious())
          ret.push_back(p->getNodeName());
        break;
      }

      int n = cur->getNumberUsed();
      for (int i = 0; i < n; ++i) {
        Node *tmp = cur->getAttachedNode(i);
        if (!tmp->isMarked()) {
          q.push(tmp->getNodeName());
          tmp->setPrevious(cur);
        }
      }
    }

    std::reverse(ret.begin(), ret.end());
    return ret;
  }

 private:
  std::map<std::string, Node *> nodes_;
};

int main(int argc, char *argv[])
{
  printf("============================================================\n"
         "|        Welcome to the Shortest Path Maze Solver!         |\n"
         "============================================================\n");

  while (1) {
    std::string fname;
    printf("\nEnter the name of the Maze configuration file: ");
    getline(std::cin, fname);

    if (!fname.compare("Quit"))
      break;

    std::ifstream fin(fname.c_str());
    if (!fin) {
      fprintf(stderr, "\nE: No file named %s\n", fname.c_str());
      continue;
    }

    int n;
    fin >> n;

    std::string start, dest;
    fin >> start >> dest;

    printf("The Start Node is: %s\n"
           "The Destination Node is: %s\n",
           start.c_str(), dest.c_str());

    Maze m;
    std::string from, to;
    for (std::string line; getline(fin, line); ) {
      std::stringstream ss(line);
      ss >> from;
      while (ss >> to) m.add_edge(from, to);
    }

    printf("\nFinding the shortest path from the Start to the Destination node ...\n"
           "\nNode visited:");

    std::vector<std::string> path = m.solve(start, dest);

    if (path.empty()) {
      printf("\n\nUnsuccessful: No path can be found.\n");
    } else {
      printf("\n\nCongratulations: Found the shortest path successfully.\n"
             "The path is:");
      for (std::vector<std::string>::iterator it = path.begin();
           it != path.end(); ++it)
        printf(" %s", it->c_str());
      printf("\n");
    }
  }

  printf("============================================================\n"
         "|    Thank you for using the Shortest Path Maze Solver!    |\n"
         "============================================================\n");

  return 0;
}

maze1.txt

48
B3
H4
A1 A2 B1
B1 B2 A1
C1 C2
D1 D2 E1
E1 D1
F1 F2
G1 G2 H1
H1 G1
A2 A3 A1 B2
B2 C2 B1 A2
C2 D2 C1 B2
D2 D3 D1 C2
E2 E3 F2
F2 F3 G2 F1 E2
G2 H2 G1 F2
H2 H3 G2
A3 B3 A2
B3 B4 A3
C3 C4 D3
D3 E3 D2 C3 D4
E3 E2 D3
F3 F4 F2
G3 G4
H3 H4 H2
A4 A5 B4
B4 B5 B3 A4
C4 D4 C3
D4 E4 C4 D3
E4 E5 F4 D4
F4 G4 F3 E4
G4 G3 F4
H4 H5 H3
A5 A6 A4
B5 C5 B4
C5 C6 D5 B5
D5 C5 E5
E5 E6 F5 E4 D5
F5 E5
G5 G6 H5
H5 H4 G5
A6 B6 A5
B6 A6
C6 C5
D6 E6
E6 F6 E5 D6
F6 E6 G6
G6 H6 G5 F6
H6 G6