Reči u mreži – Word Search (backtracking i pretraga)

Zadatak:
Dati su mreža od m redova i n kolona koja sadrži mala slova engleske abecede, i reč s. Napiši program koji proverava da li se reč s može pronaći u mreži. Reč se može formirati kretanjem susednim ćelijama u četiri osnovna pravca (gore-dole, levo-desno). Svaka ćelija sme biti korišćena najviše jednom u formiranju reči.

Ulaz: Sa standardnog ulaza unose se brojevi m i n (1 ≤ m,n ≤ 200), zatim mreža od m redova sa n slova u svakom, i na kraju reč s (dužina ≤ m·n).
Izlaz: Ispisati YES ako se reč može pronaći, inače NO.

Primer:

Ulaz:
3 4
abcd
efgh
ijkl
fghe

Izlaz:
YES
  

Uputstvo i ideja rešenja

Ovaj problem je klasičan primer kombinovanja pretrage po dubini (DFS) sa backtracking-om. Koraci su sledeći:

• Za svaku ćeliju mreže koja sadrži prvo slovo reči s, pokreni DFS / rekurziju.
• U DFS-u: označi trenutno polje kao posećeno (ne možeš ga ponovo koristiti), i proveri sve četiri moguće susedne ćelije.
• Ako sledeće slovo odgovara susednoj ćeliji i ta ćelija nije posećena, nastavi rekurzivno.
• Ako si uspeo da pokriješ sva slova reči → vrati true (YES). Ako ne, nakon pokušaja vraćaš stanje (undo označavanje) i nastavljaš sledeću mogućnost (backtracking).

Rešenje u C++ jeziku

#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;
}
  

Objašnjenje koda

Program prvo učitava dimenzije i mrežu i reč.
Zatim ide kroz svaku ćeliju — ako ćelija odgovara prvom slovu reči, startuje DFS.

• used[x][y] obilježava da je ćelija već korišćena u trenutnom putu.
• Funkcija dfs(x, y, idx) znači: „trenutno sam na poziciji (x,y) i tražim slovo s[idx]”. Ako idx == s.size() → pronađena je cela reč.
• Unutar DFS-a se pregleda 4 susedna pravca. Ako uslov odgovara (unutra je, nije korišćeno, slično je slovo) → nastavlja se. Ako uspe → vraćamo true. Inače — vraćamo stanje (used[x][y] = false) i nastavljamo sledeći pravac (backtracking).

Komentar o efikasnosti i poboljšanjima

Ovaj osnovni pristup ima složenost približno O(m·n·4^L), gde je L dužina reči, što može biti veliko za velike mreže + duge reči.

Moguća poboljšanja:

• Ograniči broj početnih pozicija: ne pokreći DFS za sve ćelije, već samo one koje odgovaraju prvom slovu.
• Koristi heuristike – prvo pronađi redove/slova koja su retka u mreži.
• Ako imaš listu mnogih reči (ne samo jednu) — koristi strukturu **Trie** + zajedničko istraživanje mreže (poput problema „Word Search II”).
• Za memorisanje – možeš koristiti bit masku za korišćena polja, radi brže promenljivosti stanja.

Varijanta 1 – osnovni DFS sa backtracking-om

Ovo je klasična implementacija problema Word Search koristeći rekurzivni DFS sa backtracking-om. Svaka ćelija se koristi najviše jednom u trenutnom putu. Ovaj pristup je najintuitivniji i edukativan.

• Korak 1: Za svako slovo koje odgovara prvom slovu reči startujemo DFS.
• Korak 2: Unutar DFS-a, označavamo ćeliju kao posećenu i rekurzivno proveravamo 4 susedna pravca.
• Korak 3: Ako pronađemo sledeće slovo u susednoj ćeliji → nastavljamo rekurzivno.
• Korak 4: Ako ne uspe → vraćamo stanje (backtracking) i proveravamo ostale pravce.
• Korak 5: Ako se uspešno pokrije cela reč → vraćamo true (YES), inače false (NO).

Prednosti Varijante 1: jednostavno i pregledno, odličan za učenje backtracking principa.

Ograničenja: složenost O(m·n·4^L), gde je L dužina reči, može biti sporo za velike mreže i duge reči.

Varijanta 2 – optimizovani DFS sa heuristikama

Ova varijanta koristi iste principe kao Varijanta 1, ali dodaje optimizacije:

• Pokrećemo DFS samo za ćelije koje odgovaraju prvom slovu reči (redukcija startnih pozicija).
• Pretraga susednih ćelija se vrši prema retkosti slova u reči → prvo tražimo rjeđa slova u mreži.
• Može se koristiti bitmask ili dodatna matrica za brže označavanje korišćenih ćelija.
• Ove optimizacije značajno smanjuju broj nepotrebnih rekurzija, naročito za duže reči i veće mreže.

Prednost Varijante 2: brža za veće mreže i više zadataka, bez promene osnovnog principa DFS + backtracking.

Varijanta 3 – rešenja sa Trie strukturom (za više reči)

Ako imamo listu više reči koje treba pronaći u istoj mreži (Word Search II), koristi se struktura Trie:

• Kreiramo Trie od svih reči koje tražimo.
• Pokrećemo DFS od svake ćelije mreže, ali prolazimo kroz Trie → odmah prekidamo put ako ne postoji odgovarajući prefix.
• Na ovaj način pronalazimo više reči u jednoj DFS pretrazi mreže, čime značajno smanjujemo kompleksnost u odnosu na pojedinačni DFS za svaku reč.

Prednost Varijante 3: optimalno za više reči, efikasno i skalabilno; često se koristi u takmičarskom programiranju.

Napomena za sve varijante: osnovni princip ostaje backtracking, sa označavanjem posećenih ćelija i vraćanjem stanja kada pretraga ne uspe.

Varijanta 2 – optimizovani DFS sa heuristikama

Ova varijanta koristi isti osnovni princip DFS + backtracking kao Varijanta 1, ali dodaje optimizacije kako bi pretraga bila brža, posebno za veće mreže ili duže reči.

Ideja i optimizacije:

• DFS se pokreće samo iz ćelija koje sadrže prvo slovo reči, čime se značajno smanjuje broj početnih pozicija.
• Prilikom izbora susednih ćelija, prvo proveravamo retka slova u reči – ovo smanjuje nepotrebne rekurzije.
• Korišćenje matrice ili bitmask-a za označavanje korišćenih ćelija omogućava brže vraćanje stanja (backtracking).
• Mreža se može iterirati tako da se prekine čim se pronađe reč – dodatno ubrzava izvršavanje.

Rešenje u C++ jeziku

#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 };

// Funkcija za brojanje koliko puta se pojavljuje slovo u mreži (heuristika)
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;

    // Kreiramo listu susednih pravaca i sortiramo ih prema retkosti sledećeg slova
    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});
    }

    // Sortiranje suseda po retkosti slova u mreži (heuristika)
    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;
}
  

Objašnjenje koda

• Funkcija countChar() služi da proceni retkost određenog slova u mreži, što je osnov heuristike pri izboru susednih ćelija.
• DFS sada prvo istražuje susede sa retkim slovima, smanjujući nepotrebne rekurzije i ubrzavajući pronalaženje reči.
• Označavanje korišćenih ćelija (used[x][y]) i vraćanje stanja (backtracking) ostaje isto kao u Varijanti 1.
• Glavna petlja pokreće DFS samo sa ćelija koje sadrže prvo slovo reči.

Komentar o efikasnosti

Ova varijanta je brža od osnovnog DFS-a, posebno kada su mreža i reč veći. Heuristika izbora retkih slova smanjuje broj nepotrebnih rekurzija, što je korisno u takmičarskom programiranju ili kod više zahteva u realnom vremenu.

Rešenje u Python-u (Varijanta 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")

Rešenje u C#-u (Varijanta 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");
    }
}

Varijanta 3 – više reči koristeći Trie

Ova varijanta se koristi kada želimo pronaći više reči u istoj mreži (Word Search II). Umesto da pokrećemo DFS za svaku reč posebno, gradimo Trie od svih reči i koristimo ga za optimizovanu pretragu mreže.

Ideja rešenja:

• Kreiramo Trie od svih reči koje tražimo.
• DFS počinjemo iz svake ćelije mreže, prolazeći kroz Trie – ako prefix ne postoji, odmah prekidamo put.
• Kada se dođe do kraja reči u Trie, dodajemo reč u rezultat.
• Označavamo korišćene ćelije u trenutnom putu i vraćamo stanje (backtracking) kada pretraga ne uspe.

Rešenje u C++ jeziku

#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 = ""; // da ne ponavljamo
    }
    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;
}
  

Rešenje u Python-u

m, n, k = map(int, input().split())
board = [list(input().strip()) for _ in range(m)]
words = [input().strip() for _ in range(k)]

# Trie implementacija
trie = {}
for w in words:
    node = trie
    for c in w:
        node = node.setdefault(c, {})
    node['$'] = w  # kraj reči

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['$']  # izbegavamo duplikate
    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))

Rešenje u C#-u

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; // ne duplirati
        }
        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);
    }
}

Komentar o efikasnosti

Ova varijanta značajno smanjuje ukupno vreme pretrage u odnosu na pojedinačni DFS za svaku reč. Korišćenjem Trie strukture odmah prekidamo putove koji ne vode do nijedne reči, što je idealno za takmičarsko programiranje i veće mreže sa više reči.

Izvori i reference

Neki zadaci i ideje algoritama inspirisani su sledećim izvorima, ali svi kodovi i objašnjenja su originalni i prilagođeni za SvetProgramiranja:

• GeeksforGeeks – Knight's Tour Problem
• LeetCode – arhiva zadataka (N-Queens, Word Search, Sudoku)
• Petlja / Takprog – srednjoškolski zadaci iz algoritama

Napomena: svi kodovi su kreirani posebno za SvetProgramiranja i prilagođeni za edukativnu upotrebu.