// Maze (mjd@cs.auckland.ac.nz) // #include #include #include #include #include using namespace std; typedef vector NLIST; // node (neighbor) list typedef vector< NLIST > ADJLIST; // graph data structure class Graph { private: ADJLIST adj; // adjacency lists. public: // creators + destroyers // Graph(int n) : adj(n) { } ~Graph() {} // stream I/0 // friend ostream& operator<<(ostream&, const Graph&); friend istream& operator>>(istream&, Graph&); // mutators // bool addEdge(int u, int v) // false if already exists { if ( isEdge(u,v) ) return false; adj[u].push_back(v); return true; } bool rmEdge(int u, int v) // false if doesn't exist { int n = order(); const NLIST::iterator it = find( adj[u].begin(), adj[u].end(), v ); if ( it==adj[u].end() ) return false; adj[u].erase(it); return true; } // accessors // int order() const { return adj.size(); } bool isEdge(int u, int v) const { int n = order(); NLIST::const_iterator it = find( adj[u].begin(), adj[u].end(), v ); if ( it==adj[u].end() ) return false; else return true; } int degree(int u) const { return adj[u].size(); } const NLIST neighbors(int u) const { return (const NLIST&) adj[u]; } }; ostream& operator<<(ostream& o, const Graph& G) { o << G.order() << "\n"; for (int i=0; i>(istream& in, Graph& G) { char line[LLEN]; int n; in.getline(line, LLEN); istringstream lineIn(line); lineIn >> n; G.adj.resize(n); for (int i=0; i>v2) { G.addEdge(v1,v2); } } return in; } //****************************************************************** int minPath(const Graph &G, int s, int t) { int n = G.order(); NLIST dist(n); for (int i=0; i 0 ) { depth++; NLIST nextList; for (int i=0; i < distList.size(); i++ ) { const NLIST nbrs = G.neighbors(distList[i]); for (int k=0; k < nbrs.size(); k++) { int u = nbrs[k]; if (dist[u] == n) { if (u==t) return depth; dist[u] = depth; cnt++; nextList.push_back(u); } } } distList = nextList; // next try set of vertices further away } return -1; } int main(int argc, char **argv) { int n, m; int i, j; int graphCount=1; while (1) { cin >> n >> m; if (n==0) break; Graph G(n*m+1); // one vertex for outside maze. cout << "Maze " << (graphCount++); vector Maze; string str; getline(cin,str); // finish title line for (i=0; i<2*m+1; i++) { getline(cin,str); Maze.push_back(str); } int s; for (i=0; i0 && Maze[2*i+1][2*j]==' ') G.addEdge(i*n+j, i*n+(j-1)); if (j0 && Maze[2*i][2*j+1]==' ') G.addEdge(i*n+j, (i-1)*n+j); if (i