boggle.cpp

C++&datastructure书籍源码,以前外教提供现在与大家共享

#include <iostream>
#include <string>
#include <fstream>
#include <iomanip>
using namespace std;

#include "linkset.h"
#include "tvector.h"
#include "tmatrix.h"
#include "point.h"
#include "randgen.h"
#include "prompt.h"

class Boggle
{
  public:
    Boggle(int size);
    
    void MakeBoard();
    
    bool OnBoard(const string& s);
    bool OnBoard(const string& s, tvector<Point>& locations);
    
    void Print() const;
    
  private:
    typedef LinkSet<Point>         PointSet;
    typedef LinkSetIterator<Point> PointSetIterator;
    
    tmatrix<char>     myBoard;
    tvector<PointSet> myLetterLocs;
    PointSet          myVisited;
    
    bool IsAdjacent(const Point& p, const Point& q);
    bool OnBoardAt(const string& s, const Point& p, tvector<Point>& locs);
    
};

Boggle::Boggle(int size)
 : myBoard(size,size),
   myLetterLocs(26)
{

}

void Boggle::MakeBoard()
{
    static string vowels=  "aeiouy";
    static string commons= "tnshrdlm";
    static string others=  "bcfgjkpqvwxz";
    RandGen gen;
    int j,k;
    string choice;
    for(j=0; j < myBoard.numrows(); j++)
    {   for(k=0; k < myBoard.numcols(); k++)
        {   choice = others;
            int pick = gen.RandInt(1,6);
            if (pick <= 3)
            {   choice = vowels;
            }
            else if (pick <= 5)
            {   choice = commons;
            }
            myBoard[j][k] = choice[gen.RandInt(0,choice.length()-1)];
            myLetterLocs['z'-myBoard[j][k]].insert(Point(j,k));
         }
     }
}

bool Boggle::IsAdjacent(const Point& p, const Point& q)
{
    if (p.x == -1 || q.x == -1) return true;
    int rowdiff = p.x - q.x;
    int coldiff = p.y - q.y;
    return p != q && rowdiff*rowdiff + coldiff*coldiff <= 2;
}

bool Boggle::OnBoardAt(const string& s, const Point& p, tvector<Point>& locs)
{
    if (s.length() == 0) return true;
    
    PointSet ps = myLetterLocs['z' - s[0]];
    PointSetIterator psi(ps);
    for(psi.Init(); psi.HasMore(); psi.Next())
    {   Point nextp = psi.Current();
        if (IsAdjacent(p,nextp) && ! myVisited.contains(nextp))
        {   myVisited.insert(nextp);
            locs.push_back(nextp);
            if (OnBoardAt(s.substr(1,s.length()-1),nextp,locs))
            {   return true;
            }
            locs.pop_back();
            myVisited.erase(nextp);
        }
    }
    return false;
}

bool Boggle::OnBoard(const string& s, tvector<Point>& locations)
{
    myVisited.clear();
    locations.clear();
    return OnBoardAt(s, Point(-1,-1), locations);
}

bool Boggle::OnBoard(const string& s)
{
   tvector<Point> dummy;
   return OnBoard(s,dummy);
}

void Boggle::Print() const
{
    int j,k;
    for(j=0; j < myBoard.numrows(); j++)
    {   for(k=0; k < myBoard.numcols(); k++)
        {   cout << setw(3) << myBoard[j][k];
        }
        cout << endl;
    }
}

void Print(const tvector<Point>& v)
{
    int k;
    for(k=0; k < v.size(); k++)
    {   cout << v[k] << " ";
    }
    cout << endl;
}

int main()
{
    int size = PromptRange("boggle size ",3,8);
    Boggle bog(size);
    
    bog.MakeBoard();
    bog.Print();
    
    string word;
    tvector<Point> locs;
    string filename = PromptString("words ");
    ifstream input(filename.c_str());
    while (input >> word)
    {   if (bog.OnBoard(word,locs))
        { cout << word << "\t"; Print(locs);
        }
        else
        {   // cout << "not found" << endl;
        }
    }
    bog.Print();
    
    return 0;
}