You are given a rectangular grid of lowercase letters and a target word. Starting from any cell, you may move to an orthogonally adjacent cell (up, down, left, or right — never diagonally), and you may never revisit a cell already used earlier in the same trace. Determine whether there exists some sequence of moves that spells out the target word exactly, one letter per visited cell in order.
Line 1: two integers rows and cols.
Next rows lines: each a string of exactly cols lowercase letters — one row of the grid.
Last line: the target word (a non-empty string of lowercase letters).
Print 1 if the word can be traced, otherwise print 0.
Example 1
Input
2 2 ab ba aba
Expected
1
Explanation
Starting at row 0, col 0 ('a'), move right to ('b'), then down to ('a') at row 1, col 1 — tracing the word "aba" step by step, so the answer is 1.
Example 2
Input
2 2 ab ba bb
Expected
0
Explanation
The two 'b' cells are at row 0, col 1 and row 1, col 0, which are not orthogonally adjacent, and no other cell holds 'b'. The word "bb" cannot be traced, so the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →