SBACT - Slow Growing Bacteria

no tags 

Given an nxn grid of cells, a bacteria colony can colonize these cells. Their growth after every second is governed by the following rules:

  1. One new bacteria is born in cell (i, j) if and only if either one of its four neighboring cells or the cell (i, j) itself has a bacteria population more than or equal to the threshold value, k.
  2. Already living bacteria do not die.

Given, the initial state of the nxn cell grid, you need to accurately estimate the time by when the total bacteria population reaches m.

Input

First line contains t, number of test cases.

Each test case starts with n (side length of grid), k (growth threshold) and m (final population).

Next n lines contain an nxn grid of integers, where ith row, jth column has an integer representing the number of bacteria present initially at cell (i, j).

1< n <= 100, 0 < k <= 2^45, 0 < m <= 2^45.

There are no more than n cells with initial population equal to or greater than k.

Output

For each test case print the number of seconds required for the total bacteria population to reach m. If m can never be reached print "Not possible" (quotes for clarity).

Example

Input:
1
3 5 15
0 0 0
0 3 0
0 0 5

Output:
3

hide comments
hodobox: 2017-04-30 15:27:26

Assert fails on t<100, passes on t<=100 :)

Last edit: 2017-04-30 15:28:51
:D: 2012-05-11 17:34:36

Unfortunately, that's an issue with many problems. You have everything specified but still you are left with guessing number of test cases itself.

Stefan: 2012-05-08 17:03:19

Could we, by any means, get the maximum value of t?


Added by:Prof_Utonium_ಉಮೆಶ್
Date:2010-10-05
Time limit:0.509s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-RHINO OBJC SQLITE
Resource:MNNIT IOPC 2010, Co-author: jitendra_kumar