ALLIZWEL - ALL IZZ WELL

Mr.ESP used to tell “ALL IZZ WELL” whenever he gets into any trouble. So his friends and the people around him used to laugh at him. But Mr.ESP is very strong in his belief. He believes that the term “ALL IZZ WELL” will make everything fine. Now your task is to ignore the story above and find whether there is a path in the given matrix which makes the sentence “ALL IZZ WELL”

There is a path from any cell to all its neighbouring cells. A neighbour may share an edge or a corner.

Input Specification:

The first line consists of an integer t representing the number of test cases.

The first line of each test case consists of two integers R and C representing the number of rows and number of columns in the matrix. The description of the matrix follows.

Output Specification:

For each test case print “YES” if there is a path which makes the sentence “ALLIZZWELL”. Else print “NO”.

Note: Take care of 4th test case

There is a new line after every test case in the input.

Input constraints:

t <= 1000
R <= 100
C <= 100

Sample Input:

5
3 6
AWE.QX
LLL.EO
IZZWLL

1 10
ALLIZZWELL

2 9
A.L.Z.E..
.L.I.W.L.

3 3
AEL
LWZ
LIZ

1 10
LLEWZZILLA
Sample Output:
YES
YES
NO
NO
YES

Added by:cegprakash
Date:2011-12-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-12-27 05:49:47 kelaseek
thala i am getting wa .. i have tried almost all cases available on the internet
2014-12-24 16:59:02 Karan2k
output for the test case :
1
4 4
AEW.
LLIZ
LL.Z
should be YES
2014-12-09 09:38:24 eti goel
1
3
3
AIZ
PLZ
REW

wat should be its answer ?
2014-11-23 10:48:26 Rohan Jain
GOT IT...
DFS...


Last edit: 2014-11-23 18:40:39
2014-11-07 09:48:58 Ankur Singh
dfs.../
2014-10-07 13:05:35 Nikhil Teja Alamanda
Can the same node be used again? Like in this test case:
W A L E W
L I L Z K
Z H X F U
The last two L s can be reused here.
2014-09-25 00:55:17 Baojun Wang
ABCPATH is a simple version of this one.
2014-09-03 20:13:00 Garima
Test cases of this problem are very weak.
Two different AC solutions give different answers for the test case:
Input:
1
4 5
AL###
%L***
ZI()@
ZWELL
Correct Output should be Yes.

Last edit: 2014-09-04 07:57:26
2014-08-27 09:55:01 Ajay Prasadh
accepted no better feeling and thanks for the useful comments .take care of visited !

Last edit: 2014-08-27 09:55:56
2014-08-19 20:58:07 Pratyush Kumar
for those getting wrong answer be certain to mark the visited node, and unmark the visited node if bactrack fails . :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.