Words in a Grid – Word Search (backtracking and search)
Task:
We are given a grid of m rows and n columns that contains lower case letters of the English alphabet, and a word s.
Write a program that checks whether the word s can be found in the grid. The word can be formed by moving through neighbouring cells in the four basic directions (up-down, left-right). Every cell may be used at most once in forming the word.
Input: The standard input contains the numbers m and n (1 ≤ m,n ≤ 200), then a grid of m rows with n letters in each, and finally the word s (length ≤ m·n).
Output: Print YES if the word can be found, otherwise NO.
Example:
Input: 3 4 abcd efgh ijkl fgkj Output: YES
Hints and the idea of the solution
This problem is a classic example of combining depth-first search (DFS) with backtracking. The steps are:
- For every cell of the grid that contains the first letter of the word s, start a DFS / recursion.
- In the DFS: mark the current cell as visited (you cannot use it again), and check all four possible neighbouring cells.
- If the next letter matches a neighbouring cell and that cell has not been visited, continue recursively.
- If you managed to cover all letters of the word → return true (YES). If not, after the attempt you restore the state (undo the marking) and continue with the next possibility (backtracking).
Solution in C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int m, n;
vector<string> grid;
string s;
vector<vector<bool>> used;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool dfs(int x, int y, int idx) {
if (idx == (int)s.size()) return true;
used[x][y] = true;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && nx < m && ny >= 0 && ny < n
&& !used[nx][ny] && grid[nx][ny] == s[idx]) {
if (dfs(nx, ny, idx + 1)) return true;
}
}
used[x][y] = false;
return false;
}
int main() {
cin >> m >> n;
grid.resize(m);
for (int i = 0; i < m; i++) {
cin >> grid[i];
}
cin >> s;
used.assign(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == s[0]) {
if (dfs(i, j, 1)) {
cout << "YES\n";
return 0;
}
}
}
}
cout << "NO\n";
return 0;
}
Explanation of the code
The program first reads the dimensions, the grid and the word.
Then it goes through every cell — if the cell matches the first letter of the word, it starts a DFS.
used[x][y]marks that the cell has already been used in the current path.- The function
dfs(x, y, idx)means: "I am currently at position (x,y) and I am looking for the letter s[idx]". If idx == s.size() → the whole word has been found. - Inside the DFS the 4 neighbouring directions are examined. If the condition holds (inside the grid, not used, the same letter) → the search continues. If it succeeds → we return true. Otherwise — we restore the state (used[x][y] = false) and continue with the next direction (backtracking).
A comment on efficiency and improvements
This basic approach has a complexity of approximately O(m·n·4^L), where L is the length of the word, which can be large for big grids + long words.
Possible improvements:
- Limit the number of starting positions: do not start a DFS from all cells, only from those that match the first letter.
- Use heuristics – first look for rows/letters that are rare in the grid.
- If you have a list of many words (not just one) — use a Trie structure + a shared exploration of the grid (like the problem "Word Search II").
- For remembering – you can use a bit mask for the used cells, so that the state changes faster.
Variant 1 – basic DFS with backtracking
This is the classic implementation of the Word Search problem using recursive DFS with backtracking. Every cell is used at most once in the current path. This approach is the most intuitive and educational.
- Step 1: For every letter that matches the first letter of the word we start a DFS.
- Step 2: Inside the DFS, we mark the cell as visited and recursively check the 4 neighbouring directions.
- Step 3: If we find the next letter in a neighbouring cell → we continue recursively.
- Step 4: If it does not succeed → we restore the state (backtracking) and check the other directions.
- Step 5: If the whole word is covered successfully → we return
true(YES), otherwisefalse(NO).
Advantages of Variant 1: simple and clear, excellent for learning the principle of backtracking.
Limitations: the complexity O(m·n·4^L), where L is the length of the word, can be slow for big grids and long words.
Variant 2 – optimized DFS with heuristics
This variant uses the same principles as Variant 1, but adds optimizations:
- We start a DFS only from the cells that match the first letter of the word (fewer starting positions).
- The neighbouring cells are searched according to how rare the letters are → first we look for the letters that are rarer in the grid.
- A bitmask or an additional matrix can be used for faster marking of the used cells.
- These optimizations significantly reduce the number of unnecessary recursive calls, especially for longer words and bigger grids.
Advantage of Variant 2: faster for bigger grids and more tasks, without changing the basic principle of DFS + backtracking.
Variant 3 – solutions with a Trie structure (for several words)
If we have a list of several words that have to be found in the same grid (Word Search II), a Trie structure is used:
- We build a Trie from all the words we are looking for.
- We start a DFS from every cell of the grid, but we move through the Trie → we stop a path immediately if there is no matching prefix.
- In this way we find several words in one DFS search of the grid, which significantly reduces the complexity compared with a separate DFS for every word.
Advantage of Variant 3: optimal for several words, efficient and scalable; it is often used in competitive programming.
A note for all variants: the basic principle stays backtracking, with marking the visited cells and restoring the state when the search does not succeed.
Variant 2 – optimized DFS with heuristics
This variant uses the same basic principle of DFS + backtracking as Variant 1, but adds optimizations to make the search faster, especially for bigger grids or longer words.
The idea and the optimizations:
- The DFS is started only from the cells that contain the first letter of the word, which significantly reduces the number of starting positions.
- When choosing the neighbouring cells, we first check the rare letters of the word – this reduces unnecessary recursive calls.
- Using a matrix or a bitmask to mark the used cells makes restoring the state (backtracking) faster.
- The grid can be traversed so that the search stops as soon as the word is found – this speeds up the execution even more.
Solution in C++
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int m, n;
vector<string> grid;
string s;
vector<vector<bool>> used;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
// A function that counts how many times a letter appears in the grid (heuristic)
int countChar(char c) {
int cnt = 0;
for (int i = 0; i < m; i++)
cnt += count(grid[i].begin(), grid[i].end(), c);
return cnt;
}
bool dfs(int x, int y, int idx) {
if (idx == (int)s.size()) return true;
used[x][y] = true;
// We make a list of neighbouring directions and sort them by how rare the next letter is
vector<pair<int,int>> neighbors;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && nx < m && ny >= 0 && ny < n
&& !used[nx][ny] && grid[nx][ny] == s[idx])
neighbors.push_back({nx, ny});
}
// Sorting the neighbours by how rare the letter is in the grid (heuristic)
sort(neighbors.begin(), neighbors.end(), [&](pair<int,int> a, pair<int,int> b){
return countChar(grid[a.first][a.second]) < countChar(grid[b.first][b.second]);
});
for (auto &p : neighbors) {
if (dfs(p.first, p.second, idx + 1)) return true;
}
used[x][y] = false;
return false;
}
int main() {
cin >> m >> n;
grid.resize(m);
for (int i = 0; i < m; i++) cin >> grid[i];
cin >> s;
used.assign(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == s[0]) {
if (dfs(i, j, 1)) {
cout << "YES\n";
return 0;
}
}
}
}
cout << "NO\n";
return 0;
}
Explanation of the code
- The function
countChar()is used to estimate how rare a letter is in the grid, which is the basis of the heuristic for choosing the neighbouring cells. - The DFS now first explores the neighbours with rare letters, reducing unnecessary recursive calls and finding the word faster.
- Marking the used cells (
used[x][y]) and restoring the state (backtracking) stay the same as in Variant 1. - The main loop starts a DFS only from the cells that contain the first letter of the word.
A comment on efficiency
This variant is faster than the basic DFS, especially when the grid and the word are bigger. The heuristic of choosing rare letters reduces the number of unnecessary recursive calls, which is useful in competitive programming or with many requests in real time.
Solution in Python (Variant 2)
m, n = map(int, input().split())
grid = [input().strip() for _ in range(m)]
s = input().strip()
used = [[False] * n for _ in range(m)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def count_char(c):
return sum(row.count(c) for row in grid)
def dfs(x, y, idx):
if idx == len(s):
return True
used[x][y] = True
neighbors = []
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if 0 <= nx < m and 0 <= ny < n and not used[nx][ny] and grid[nx][ny] == s[idx]:
neighbors.append((nx, ny))
neighbors.sort(key=lambda p: count_char(grid[p[0]][p[1]]))
for nx, ny in neighbors:
if dfs(nx, ny, idx + 1):
return True
used[x][y] = False
return False
found = False
for i in range(m):
for j in range(n):
if grid[i][j] == s[0]:
if dfs(i, j, 1):
found = True
break
if found:
break
print("YES" if found else "NO")
Solution in C# (Variant 2)
using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static int m, n;
static char[,] grid;
static string s;
static bool[,] used;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
static int CountChar(char c) {
int cnt = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i,j] == c) cnt++;
return cnt;
}
static bool Dfs(int x, int y, int idx) {
if (idx == s.Length) return true;
used[x,y] = true;
List<(int,int)> neighbors = new List<(int,int)>();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < m && ny >= 0 && ny < n
&& !used[nx,ny] && grid[nx,ny] == s[idx])
neighbors.Add((nx, ny));
}
neighbors.Sort((a,b) => CountChar(grid[a.Item1,a.Item2]) - CountChar(grid[b.Item1,b.Item2]));
foreach (var p in neighbors)
if (Dfs(p.Item1, p.Item2, idx + 1)) return true;
used[x,y] = false;
return false;
}
static void Main() {
var tokens = Console.ReadLine().Split();
m = int.Parse(tokens[0]);
n = int.Parse(tokens[1]);
grid = new char[m,n];
for (int i = 0; i < m; i++) {
var line = Console.ReadLine();
for (int j = 0; j < n; j++) grid[i,j] = line[j];
}
s = Console.ReadLine();
used = new bool[m,n];
bool found = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i,j] == s[0] && Dfs(i, j, 1)) {
found = true;
break;
}
}
if (found) break;
}
Console.WriteLine(found ? "YES" : "NO");
}
}
Variant 3 – several words using a Trie
This variant is used when we want to find several words in the same grid (Word Search II). Instead of starting a DFS for every word separately, we build a Trie from all the words and use it for an optimized search of the grid.
The idea of the solution:
- We build a Trie from all the words we are looking for.
- We start the DFS from every cell of the grid, moving through the Trie – if the prefix does not exist, we stop the path immediately.
- When we reach the end of a word in the Trie, we add the word to the result.
- We mark the used cells in the current path and restore the state (backtracking) when the search does not succeed.
Solution in C++
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
struct TrieNode {
TrieNode* children[26] = {};
string word = "";
};
void insert(TrieNode* root, const string& word) {
TrieNode* node = root;
for(char c : word){
int idx = c - 'a';
if(!node->children[idx]) node->children[idx] = new TrieNode();
node = node->children[idx];
}
node->word = word;
}
int dx[4] = {-1,1,0,0}, dy[4]={0,0,-1,1};
vector<string> result;
void dfs(vector<vector<char>>& board, int x, int y, TrieNode* node){
char c = board[x][y];
int idx = c - 'a';
if(!node->children[idx]) return;
node = node->children[idx];
if(node->word != "") {
result.push_back(node->word);
node->word = ""; // so that we do not repeat it
}
board[x][y] = '#';
int m = board.size(), n = board[0].size();
for(int d=0; d<4; d++){
int nx = x + dx[d], ny = y + dy[d];
if(nx >=0 && nx < m && ny >=0 && ny < n && board[nx][ny] != '#')
dfs(board, nx, ny, node);
}
board[x][y] = c;
}
int main(){
int m, n, k;
cin >> m >> n >> k;
vector<vector<char>> board(m, vector<char>(n));
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin >> board[i][j];
vector<string> words(k);
for(int i=0;i<k;i++) cin >> words[i];
TrieNode* root = new TrieNode();
for(auto &w : words) insert(root, w);
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
dfs(board,i,j,root);
for(auto &w: result) cout << w << endl;
}
Solution in Python
m, n, k = map(int, input().split())
board = [list(input().strip()) for _ in range(m)]
words = [input().strip() for _ in range(k)]
# Trie implementation
trie = {}
for w in words:
node = trie
for c in w:
node = node.setdefault(c, {})
node['$'] = w # end of the word
dx = [-1,1,0,0]
dy = [0,0,-1,1]
res = []
def dfs(x, y, node):
c = board[x][y]
if c not in node:
return
nxt = node[c]
if '$' in nxt:
res.append(nxt['$'])
del nxt['$'] # we avoid duplicates
board[x][y] = '#'
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if 0 <= nx < m and 0 <= ny < n and board[nx][ny] != '#':
dfs(nx, ny, nxt)
board[x][y] = c
for i in range(m):
for j in range(n):
dfs(i, j, trie)
print('\n'.join(res))
Solution in C#
using System;
using System.Collections.Generic;
class TrieNode {
public Dictionary<char, TrieNode> children = new Dictionary<char, TrieNode>();
public string word = null;
}
class Program {
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static List<string> res = new List<string>();
static void Dfs(char[,] board, int x, int y, TrieNode node) {
char c = board[x,y];
if(!node.children.ContainsKey(c)) return;
node = node.children[c];
if(node.word != null) {
res.Add(node.word);
node.word = null; // do not duplicate
}
board[x,y] = '#';
int m = board.GetLength(0), n = board.GetLength(1);
for(int d=0; d<4; d++){
int nx = x + dx[d], ny = y + dy[d];
if(nx >=0 && nx < m && ny >=0 && ny < n && board[nx,ny] != '#')
Dfs(board, nx, ny, node);
}
board[x,y] = c;
}
static void Main() {
var tokens = Console.ReadLine().Split();
int m = int.Parse(tokens[0]);
int n = int.Parse(tokens[1]);
int k = int.Parse(tokens[2]);
char[,] board = new char[m,n];
for(int i=0;i<m;i++){
var line = Console.ReadLine();
for(int j=0;j<n;j++) board[i,j] = line[j];
}
TrieNode root = new TrieNode();
List<string> words = new List<string>();
for(int i=0;i<k;i++){
string w = Console.ReadLine();
words.Add(w);
TrieNode node = root;
foreach(char c in w){
if(!node.children.ContainsKey(c)) node.children[c] = new TrieNode();
node = node.children[c];
}
node.word = w;
}
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
Dfs(board, i, j, root);
foreach(var w in res) Console.WriteLine(w);
}
}
A comment on efficiency
This variant significantly reduces the total search time compared with a separate DFS for every word. By using the Trie structure we immediately stop the paths that do not lead to any word, which is ideal for competitive programming and bigger grids with several words.
Sources and references
Some tasks and algorithm ideas were inspired by the following sources, but all the code and explanations are original and adapted for Svet programiranja:
- GeeksforGeeks – Knight's Tour Problem
- LeetCode – task archive (N-Queens, Word Search, Sudoku)
- Petlja / Takprog – secondary school algorithm tasks (in Serbian)
Note: all the code was created especially for Svet programiranja and adapted for educational use.
Previous
|<Preparation for the national competition and SIO
