wordgame.cpp

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

bool Boggle::OnBoardAt(const string& s, const Point& p, tvector<Point>& locs)
// post: return true iff string s can be found on the board 
//       beginning at location p (s[0] found at p, s[1] at a location
//       adjacent to p, and so on). If found, locs stores the locations
//       of the word, locations are added using push_back
{
    if (s.length() == 0) return true;  // all letters done, found the word
    
    PointSet ps = myLetterLocs['z' - s[0]];  // set of eligible letters
    PointSetIterator psi(ps);                // try all locations
    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;   // tried all locations, word not on board
}