# LeetCode题目：Word Search，回溯

By | 2012 年 11 月 8 日

Word Search
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =

```[
["ABCE"],
["SFCS"],
]
```

word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.

```struct Pos{
int row;
int col;
Pos(int r, int c):row(r),col(c) {;}
};

class Solution {
public:
bool exist(vector > &board, string word) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int rows = board.size();
if(0 == rows) return false;
int cols = board[0].size();
if(0 == cols) return false;

if(0 == word.size()) return false;

vector trace;
trace.push_back(Pos(0,0));
bool forward = true;
while(trace.size() > 0) {
int curIndex = trace.size() - 1;
Pos &curPos = trace.back();
if(forward) {
//find a child
if(curIndex >= word.size()) return true;
char curChar = word[curIndex];
//check out of board
if( curPos.row < 0
|| curPos.row >= rows
|| curPos.col < 0
|| curPos.col >= cols ) {
forward = false;
continue;
}
//check repeat
for(int i = 0; forward && i < trace.size() - 1; ++i) {
if(trace[i].row == curPos.row && trace[i].col == curPos.col) {
forward = false;
break;
}
}
if(!forward) continue;
//go on
if(board[curPos.row][curPos.col] == curChar) {
Pos nextPos(curPos.row,curPos.col);
--nextPos.row;//position above
trace.push_back(nextPos);
} else {
forward = false;
}
} else {
if(trace.size() == 1) {
//first char in word ,find next available one
if(trace[0].row == rows - 1 && trace[0].col == cols - 1) {
//no available
trace.pop_back();
} else {
++ trace[0].col;
if(trace[0].col == cols) {
trace[0].col = 0;
trace[0].row = trace[0].row + 1;
}
forward = true;
}
} else {
Pos &lastpos = trace[trace.size() - 2];
//order as : above, right, down, left
if(curPos.col == lastpos.col) {
if(curPos.row < lastpos.row) {
//above to right
curPos.col = lastpos.col + 1;
} else {
//down to left
curPos.col = lastpos.col - 1;
}
curPos.row = lastpos.row;
forward = true;
} else {
if (curPos.col > lastpos.col) {
//right to down
curPos.row = lastpos.row + 1;
curPos.col = lastpos.col;
forward = true;
} else {
//no available
trace.pop_back();
}
}
}
}// end back if
}//end while
return false;
}
};
```