A walk on a grid
Given a n*n grid with every cell in it consisting of number 1,2 or 3. A person standing at cell (a,b) can go to (c,d) only if (c-a)+(d-b)=1 and c>=a and d>=b.
The cost of a walk is the product of all the numbers on the cells visited in that walk.
Now you have to answer q queries of the form: for each given x, y -> You start at (1,1) and end your walk in the cell (n,n), now you want to know if there is a walk such that its cost is equal to 2x*3y.
First line will contain n the dimension of the grid.
Next n ines contain n values each denoting the values in the jth cell of the ith row.
Next line contains an integer q no of queries. Next q lines contains 2 integers x and y denoting the query.
For every query print "YES"(without quotes) if there is a walk with cost 2x*3y and "NO" otherwise.
- 1 <= n <= 18
- 1 <= Ai,j <= 3
- 1 <= q <= 1000
- 1 <= x,y <= 2*n-1
Input: 5 1 2 2 3 1 1 1 1 2 3 1 2 3 1 2 1 2 2 2 2 3 3 3 3 3 1 6 1 Output: YESAll submissions for this problem are available.
|Tags||bfs, dynamic-programming, memoization, npl_nitw, nplq1602|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions