Problem Statement
You are playing word search!
The rules of the game is simple: You are given an grid of letters. You want to find if a given word, , exists on a straight line in the grid of letters.
For example, if the grid you are playing on is as follows:
WGTNPOTSFXQQ
OVOEWPCNRRLX
BDZVNXWLCXJM
NBEZPRLGXHVU
OTTPDIMJSYPJ
XNEKTUFLSFVF
JKPYJHJCYVPR
FLAUQHFWKVVA
RIKDMPJFNUJG
VTDVCECFCPXK
and if you're asked to find the word DEPTH
from it, you would be able to find it with the starting letter D
starting from nd column, rd row:
............
............
.D..........
..E.........
...P........
....T.......
.....H......
............
............
............
The word can go in any direction as long as it is in a straight line: East, North, South, West, North-East, North-West, South-East, or South-West.
As a smart kid like you are who even attends MAPS workshops, you have decided to write yourself a little algorithm that could solve word searches for you.
Input
Your first line will contain and as space-separated integers. and represents the size of the letter grid.
Your next line will contain , a string of the word you are trying to search for.
Your next lines will contain letters each, representing a single row of the letter grid.
Output
The string FOUND
if the word is present in the letter grid, nope
otherwise.
Constraints
For all test cases:
- ; that is, the word will always be able to fit on the grid.
Example 1
Input
12 10
DEPTH
WGTNPOTSFXQQ
OVOEWPCNRRLX
BDZVNXWLCXJM
NBEZPRLGXHVU
OTTPDIMJSYPJ
XNEKTUFLSFVF
JKPYJHJCYVPR
FLAUQHFWKVVA
RIKDMPJFNUJG
VTDVCECFCPXK
Output
FOUND
Example 2
Input
4 7
MONASH
QKNP
PAOA
SNMA
UHAJ
UNHS
MBSY
AOAE
Output
nope
Example 3
Input
40 36
SUPERCALIFRAGILISTICEXPIALIDOCIOUS
OOTFOBAIZIWIUDEKMUYTWIAAZLQEPQQYVFILJEVX
DNRRGLJRHJDFILAWZXCPJGGOFDKAXDLIDFDLLZUK
WXGCCMCWJIBTTDDTQSBFNFWRNQZCNAXUVKAHNNUO
MWAHYIAWGAFCEPFKLUJNKZKIRZMZXVKZRTJNNADR
BXNOKPUNCAECBZEAKOGRCTAUYLMZDRGQKFOLDBJZ
QITUYHPONZRHCBBCFIWYNQORTGOXEDAVHZTNIZND
ETGOBLKTMLAZJGTUACRJRRANJYTHCRJTHLJYYXIJ
MBPVRUOKWGVPJHOUZOUUIFWZBNAEJQBJMCIYNQRZ
OENVWIOOCAMXIXBAMDFNKHFNBAAPLCGUJGMHEKDO
HTQEOJJIGMJQVIIFGIEERMYODPCAXPYXFZMPNATC
BHGHWLAEFXKFLONNELRJHJWBURAQQJIOOFKXBHXC
HHHKENXWFVLFFRPAXADFZIBHOTQJZFWJJKYGXCDO
WJRMEWXPTZQOHAMQUIEAQYEPJZBZLCNRQXLOBQRU
PMRWAKNVDGRHDGQFGPOMTJPFOFFWHYBRXATHPHLD
OVIFBNPYUCFJIKWNNXOYYNAEQGAQDKKNRCZOTGAX
IKBULMKXLYWQWWINKELBBWVFPTQYEPHKKKULADLT
CYRFRHIDQWPPMXARZCGDEMHTTJCURIXVGGRIFFCG
OGBBJKFKBFFXWABJEIEKPJGVWVLIQFVXRQOQDOOU
KRKQRBNADPECOAEKJTEAXAHVIYUKNCNVEZDFHJEE
QMNRNRARCYFGNLYXCSXYEZVGRYCXRILUKYINDMGE
GEDBIBZQRJBJMXKMRIXCEWVLLROVEPCRKWUVVELG
MXHPMJMDOZAFYCUUTLYLCXXFBFKPXGAEBQCYPZRV
WRMVPNIHYPFZXBDDOIXBHVPVKAJCCKVIBVAQMRPV
HBNYGBKFVCWTPZREPGGDRBHQDIAXIRFMKNTDPOLQ
TJRVIYOAREOZQDEJOAYIQVXWYMPNJTWUTKGRKBBK
DVCDIEMRAATXLOJIERTGKYARTLLHITDRPRMVGBUB
CMXILELKURQKBDHVTFHQLCKNJAMGNRFPALGRVAIJ
GKLEKYJPIEFDWNIKCICFIQMZACWALKYDAXOUPRWN
RGRZBHCWHTORTXVZNLYTFWEAXBBUWHRVJPYWHARP
PVTHFGGKFJWVADPVGAOONDNWJWLAZMFXVXJMAZFK
LPLYIFXIJJKLBMVJRCCJUJMPVFQTQXMOBQWVEFYX
LDHRJBZKCAEJVVPZGRIZZETCNZIYCQACBMWGCAEJ
MKJTIQKZJGGKKNNAHEPTGKAZJWNVFNKMRPMOBFJN
OCIWIMHTGJZIXPULNPWYIGNQYRONTAUIPXXUXAVP
EFREVDIOYVIKYXQTBUJGWDTNIIHHERDXVODYWYRI
RINBUWOQZXBKFRVVKSYXFBJLHFIIAHHMVJRGLTCO
Output
FOUND
Python Template
n, m = map(int, input().split())
word = input()
board = [list(input()) for _ in range(m)]
# print(...)
Comments