- #include <iostream>
- #include <vector>
- #include <string>
- using namespace std;
- class Solution {
- private:
- int dir[4][2] = { {-1,0},{0,-1},{1,0},{0,1} };
- vector<vector<bool>>used;
- public:
- bool isCheckMove(vector<vector<char>>&map,int x, int y) {
- return x>= 0 && x <map[0].size() && y>= 0 && y <map.size();
- }
- bool Search(vector<vector<char>>&map, string& Word, int Index,int startX,int startY) {
- if (Index == Word.length() - 1) {
- return Word[Index] == map[startX][startY];
- }
- if (map[startX][startY] == Word[Index]) {
- used[startX][startY] = true;
- for (int i = 0; i <4; ++i) {
- int newX = startX + dir[i][0];
- int newY = startY + dir[i][1];
- if (isCheckMove(map, newX, newY) && !used[newX][newY] && Search(map, Word, Index + 1, newX, newY))
- {
- return true;
- }
- }
- used[startX][startY] = false;
- }
- return false;
- }
- public:
- bool SearchWord(vector<vector<char>>&map,string& Word)
- {
- used = vector<vector<bool>>(map.size(), vector<bool>(map[0].size(), false));
- for (int y = 0; y <map.size(); ++y) {
- for (int x = 0; x < map[y].size(); ++x) {
- if (map[y][x] == Word[0]&&Search(map,Word,0,y,x)) {
- return true;
- }
- else {
- continue;
- }
- }
- }
- return false;
- }
- };
- int main() {
- string Word = "bfg";
- vector<vector<char>>map = {
- {'a','b','c'},
- {'d','f','e'},
- {'g','s','h'}
- };
- if (Solution().SearchWord(map, Word)) {
- cout << "true" << endl;
- }
- else {
- cout << "false" << endl;
- }
- system("pause");
- }
来源: http://www.bubuko.com/infodetail-3229487.html