Question

How to search for a word in a grid of characters with Pascal

Answer 1

program WordSearch;

// use a depth‑first search (DFS) from every cell that matches the first letter,
// exploring all valid directions until the full word is matched. 

const
  ROWS = 3;
  COLS = 4;

type
  TGrid = array[0..ROWS-1, 0..COLS-1] of char;
  TVisited = array[0..ROWS-1, 0..COLS-1] of boolean;

function dfs(var grid: TGrid; var visited: TVisited;
             r, c: integer; word: string; index: integer): boolean;
begin
  if index = Length(word) then
  begin
    dfs := true;
    exit;
  end;

  if (r < 0) or (c < 0) or (r >= ROWS) or (c >= COLS) then
  begin
    dfs := false;
    exit;
  end;

  if visited[r][c] then
  begin
    dfs := false;
    exit;
  end;

  if grid[r][c] <> word[index+1] then
  begin
    dfs := false;
    exit;
  end;

  visited[r][c] := true;

  dfs :=
    dfs(grid, visited, r+1, c, word, index+1) or
    dfs(grid, visited, r-1, c, word, index+1) or
    dfs(grid, visited, r, c+1, word, index+1) or
    dfs(grid, visited, r, c-1, word, index+1);

  visited[r][c] := false;
end;

function wordExist(var grid: TGrid; word: string): boolean;
var
  visited: TVisited;
  r, c: integer;
begin
  FillChar(visited, SizeOf(visited), false);

  for r := 0 to ROWS-1 do
    for c := 0 to COLS-1 do
      if dfs(grid, visited, r, c, word, 0) then
      begin
        wordExist := true;
        exit;
      end;

  wordExist := false;
end;

var
  grid: TGrid;
  word: string;
  resultBool: boolean;

begin
  grid[0][0] := 'a'; grid[0][1] := 'b'; grid[0][2] := 'c'; grid[0][3] := 'e';
  grid[1][0] := 's'; grid[1][1] := 'f'; grid[1][2] := 'c'; grid[1][3] := 's';
  grid[2][0] := 'a'; grid[2][1] := 'd'; grid[2][2] := 'e'; grid[2][3] := 'e';

  word := 'see';

  resultBool := wordExist(grid, word);

  if resultBool then
    writeln('1')
  else
    writeln('0');
end.



(*
run:

1

*)

 

70+ SQL courses for beginners and professionals