Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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.
思路：dfs即可。记得要回溯一下…
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月07日 星期五 14时32分54秒
4File Name :79.cpp
5************************************************ */
6class Solution {
7
8public:
9
10 int n,m;
11 const int dx4[4]={1,-1,0,0};
12 const int dy4[4]={0,0,-1,1};
13 bool vis[1005][1005];
14 int len;
15
16 bool yes( int x,int y)
17 {
18 if (x>=0&&x<=n-1&&y>=0&&y<=m-1) return true;
19 return false;
20 }
21
22 bool dfs( int x,int y,int cur,vector<vector<char> > & maze,string & st)
23 {
24// printf("x:%d y:%d cur : %d\n",x,y,cur);
25 if (cur>=len) return true;
26 for ( int i = 0 ; i < 4 ; i++)
27 {
28 int nx = x + dx4[i];
29 int ny = y + dy4[i];
30 if (!yes(nx,ny)) continue;
31 if (vis[nx][ny]) continue;
32 if (maze[nx][ny]!=st[cur]) continue;
33 vis[nx][ny] = true;
34 bool res = dfs(nx,ny,cur+1,maze,st);
35 if (res) return true;
36 vis[nx][ny] = false ;//好像还要回溯一下啊？
37 }
38 return false;
39 }
40
41 bool exist(vector<vector<char>>& board, string word) {
42 n = board.size();
43 if (n==0) return false;
44 m = board[0].size();
45 if (m==0) return false;
46 len = word.length();
47 cout<<"len:"<<len<<endl;
48 char beg = word[0];
49 for ( int i = 0 ; i < n ; i++)
50 for ( int j = 0 ; j < m ; j++)
51 if (board[i][j]==beg)
52 {
53 memset(vis,false,sizeof(vis));
54 //起点忘记打标记了。。。智力-2.。。
55 vis[i][j] = true;
56 bool ok = dfs(i,j,1,board,word);
57 cout<<"ok:"<<ok<<endl;
58 if (ok) return true;
59 }
60 return false;
61
62
63 }
64
65};