https://leetcode.com/problems/word-search


Time Limit Exceeded


```cpp
#include <bits/stdc++.h>

using namespace std;

struct Position
{
  int x;
  int y;
};

bool does_position_in_path(Position position, vector<Position> path) {
  for (auto p : path) {
    if (p.x == position.x && p.y == position.y) {
      return true;
    }
  }
  return false;
}

bool does_this_word_inside_the_board(vector<vector<char>> &board, string word, Position position, vector<Position> path)
{
  auto height = board.size();
  auto width = board[0].size();

  if ((position.x < 0) || (position.x >= width) || (position.y < 0) || (position.y >= height))
  {
    return false;
  }

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

  auto x = position.x;
  auto y = position.y;
  if (board[y][x] == word[0] && !does_position_in_path(position, path))
  {
    if (word.size() == 1)
    {
      return true;
    }
    path.push_back(position);
    return does_this_word_inside_the_board(board, word.substr(1, word.size() - 1), Position{.x = x, .y = y - 1}, path) ||
           does_this_word_inside_the_board(board, word.substr(1, word.size() - 1), Position{.x = x, .y = y + 1}, path) ||
           does_this_word_inside_the_board(board, word.substr(1, word.size() - 1), Position{.x = x - 1, .y = y}, path) ||
           does_this_word_inside_the_board(board, word.substr(1, word.size() - 1), Position{.x = x + 1, .y = y}, path);
  }
  else
  {
    return false;
  }
}

class Solution
{
public:
  bool exist(vector<vector<char>> &board, string word)
  {
    //9:17
    for (int y = 0; y < board.size(); y++)
    {
      for (int x = 0; x < board[0].size(); x++)
      {
        vector<Position> l;
        if (does_this_word_inside_the_board(board, word, Position{x, y}, l))
        {
          return true;
        }
      }
    }
    return false;
    //9:28
    //debug until 9:31
  }
};
```