problem-1-29

You are provided a matrix of size N*N with source position at (0,0) and
destination at (N-1,N-1) in a 2D array. Some of the positions in the array are marked as 0 which are blocked cells, rest being marked 1. 

A path is a connected sequence of elements from (0,0) to (N-1,N-1) which consists of 1. A sequence of 1s in the 2D array is connected if every 1 in the sequence is adjacent (the above or left neighbour) to the next 1 in the sequence.

For example, in the following matrix,

'1'   '1'   0

0    '1'   '1'

1     0     '1'   

the 1s marked in quotes is a connected path from (0,0) to (2,2)

Note that cells at (0,0) and (N-1,N-1) are always 1. You can either make
movement towards right or down, i.e., from position (x,y), you can go to either the position (x,y+1) or (x+1,y).

Input

First line consists of the number of test cases and second line consist of size of the input array N ( ≤ 50), following that would
be the state of NxN maze which would consist of 0s and 1s.

Output

You have to print "POSSIBLE" if there exists a path between the source and the destination otherwise print "NOT POSSIBLE". 

SAMPLE INPUT
2
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
3
1 0 0
0 0 0
0 0 1

SAMPLE OUTPUT
POSSIBLE
NOT POSSIBLE

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
T = eval(input())
for t in range(T):
	possible = False
	N = eval(input())
	Maze = []
	for i in range(N):
		Maze.append(list(map(int,input().split())))
	A = [[False for x in range(N)] for x in range(N)]

	A[0][0] = True
	#print Maze	
	for x in range(N):
		for y in range(N):
			#print x, y, Maze[x][y]
			if Maze[x][y] == 1:
				if x - 1 >= 0:
					A[x][y] = A[x][y] or A[x-1][y]
				if y - 1 >= 0:
					A[x][y] = A[x][y] or A[x][y-1]
					
	possible = A[N-1][N-1]
	if possible:
		print("POSSIBLE")
	else:
		print("NOT POSSIBLE")


#!/usr/bin/python
# -*- encoding: utf-8 -*-
# pylint: disable=invalid-name,missing-docstring,bad-builtin
from sys import stdin

from collections import deque

def meet(maze, n):
	if maze[0][0]:
		queue = deque([(0, 0)])
	else:
		queue = deque()
	visited = set()
	while queue:
		x, y = queue.popleft()
		if (x, y) in visited:
			continue
		visited.add((x, y))
		if x < n - 1 and maze[x + 1][y]:
			queue.append((x + 1, y))
		if y < n - 1 and maze[x][y + 1]:
			queue.append((x, y + 1))
	return (n - 1, n - 1) in visited

def main():
	dstream = map(int, stdin.read().split())
	for _ in range(next(dstream)):
		n = next(dstream)
		maze = [[next(dstream) for _ in range(n)] for _ in range(n)]
		if meet(maze, n):
			print('POSSIBLE')
		else:
			print('NOT POSSIBLE')



main()


def solve(i,j,n):
	if i==n:
		return False
	elif j==n:
		return False
	if a[i][j]==0:
		return False
	if i==n-1 and j==n-1:
		return True
	else:
		return solve(i+1,j,n) or solve(i,j+1,n)
t=int(input())
for p in range(t):
	n=int(input())
	a=[]
	for i in range(n):
		a.append([])
	for i in range(n):
		a[i]=list(map(int,input().split()))
	if solve(0,0,n)==True:
		print("POSSIBLE")
	else:
		print("NOT POSSIBLE")



def possible(arr,a,b,size):
	if a >= size or b >=size or arr[a][b] == 0: return False
	if a == b and b == (size-1) and arr[a][b] ==1: return True
	return possible(arr, a+1, b, size) or possible(arr, a, b+1, size)
 
t = int(input())

for aa in range(t):
	size = int(input())
	arr = []
	for aa in range(size):
		arr.append([int(e) for e in  input().split(' ')])
	if possible(arr, 0, 0, size):print('POSSIBLE')
	else: print('NOT POSSIBLE')