---
cid: 39
title: No.79
slug: 39
date: 2019/06/11 09:01:00
updated: 2019/07/22 08:14:18
status: publish
author: harumonia
categories:
  - 源流清泉
  - leetcodeの解题日志
tags:
  - Algorithm \ Data Structure
thumbStyle: default
hidden: false
---

[No.79 单词搜索](https://leetcode-cn.com/problems/word-search)

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

<!-- more -->

```c++
示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
```

## 解法

这道题目可以使用回溯法来解决，这里提几个关键的地方。
line29 重置为 false，这是回溯法的关键，即将状态回滚回到递归前的状态。
line3 方向数组，配合 line22 可以将代码量压缩很多，而且逻辑关系十分清晰。

```c++
class Solution {
public:
    int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int m,n;
vector<vector<bool>> visited;

bool judge(int x,int y){
    if(x>=0 && y>=0 && y<n && x<m){
        return true;
    }
    return false;
}


bool recursion(const vector<vector<char>>& board,int startx,int starty,const string& word,int index){
    if(index==word.size()-1){
        return word[index]==board[startx][starty];
    }

    if(board[startx][starty]==word[index]){
        visited[startx][starty] = true;
        for(int i=0;i<4;i++){
            int newx = startx+d[i][0];
            int newy = starty+d[i][1];
            if(judge(newx,newy) && !visited[newx][newy] && recursion(board,newx,newy,word,index+1) ){
                return true;
            }
        }
        visited[startx][starty] = false;
    }


    return false;
}

bool exist(vector<vector<char>>& board, string word) {
    m=board.size();
    n=board[0].size();

    visited = vector<vector<bool>>(m,vector<bool>(n,false));

//    if(my==0 ) return false;

    for ( int i=0;i<m;i++){
        for (int j=0;j<n;j++){
            if(recursion(board,i,j,word,0)) return true;
        }
    }


    return false;
}
};
```