[华为机试真题]66.单词搜索

题目

代码

/*—————————————* 日期：2015-07-06* 作者：SJF0115* 题目：WordSearch* 来源：华为机试真题—————————————–*/;bool DFS(vector<vector<char> > &board,string word,int index,int x,int y,vector<vector<bool> > &visited){// 找到目标if(index == word.size()){return true;}//ifint m = board.size();if(m == 0){return false;}//ifint n = board[0].size();// 出界if(x < 0 || x >= m || y < 0 || y > n){return false;}(visited[x][y]){return false;}(board[x][y] != word[index]){return false;}//ifvisited[x][y] = true;// leftbool left = DFS(board,word,index+1,x,y-1,visited);// rightbool right = DFS(board,word,index+1,x,y+1,visited);// upbool up = DFS(board,word,index+1,x-1,y,visited);// bottombool bottom = DFS(board,word,index+1,x+1,y,visited);visited[x][y] = false;// 四个方向 任意方向找到一个即可return left || right || up || bottom;}// 单词搜索bool WordSearch(vector<vector<char> > &board,int m,int n,string word){if(n <= 0 || m <= 0 || board.empty()){return false;}<vector<bool> > visited(m,vector<bool>(n,false));// 搜索for(int i = 0;i < m;++i){for(int j = 0;j < n;++j){if(board[i][j] == word[0]){// 以board[i][j]为起点开始搜索if(DFS(board,word,0,i,j,visited)){return true;}//if}//if}//for};}int main(){int m,n;string word;//freopen(“C:\\Users\\Administrator\\Desktop\\acm.txt”,”r”,stdin);while(cin>>m>>n>>word){vector<vector<char> > board(m,vector<char>(n,0));// 输入for(int i = 0;i < m;++i){for(int j = 0;j < n;++j){cin>>board[i][j];}//for}result = WordSearch(board,m,n,word);if(result){cout<<“YES”<<endl;}//ifelse{cout<<“NO”<<endl;}//else};}

，用最少的浪费面对现在