Forgot Password ?
New password will be sent to following email id
Hybrid and his DHINCHAK POOJA craze
Problem Code : DUKH
3 0 1 0 1 1 0 0 0 0 4 2 2 0 2 0 0 2 1
Time Limit :
C , C++ , Java , Python 2
Login to submit your response.
<p> <b>hybrid</b> recently got highly affected by the statement - "Daaru Daaru Daaru, Jo na nacha usko maaru" of Dhinchak Pooja (if you know what I mean)</p> <p> The other members of the <b>HAWELI GANG</b> try to console him, but to no avail. </p> <p> <b>shivamg_isc</b> decided to give hybrid a problem in a hope that his mind may somewhat be diverted. </p> <p> <b>tejavojjala</b> liked this idea as well </p> <p> shivamg_isc asks hybrid to imagine the following scenario- </p> <p> He is in a field represented as a matrix <b>N*N</b> where <b>0 represents space and 1 represents a blockage.</b></p> <p> Rao wants to reach Teja's haweli, and find out what Teja does there. The only way to reach there is to go through this field. :P </p> <p>Rao can move in all the 8 directions.</p> <p> He can enter the field via any of the non-blockade region (if present) of the topmost row . </p> <p> He can exit the field only when he can go beyond the last row of the field. </p> <p> shivamg_isc then asks hyrbid <b>Q</b> queries. Each query will be of the form <b>"i j"</b> (without quotes) i.e <b>a blockage is added at the coordinates (i,j) , where <b>i</b> denotes the row, and <b>j</b> the column</b> </p> <p> Now hybrid has to tell shivamg_isc that <b>from which particular query it shall become impossible to cross the field.</b> </p> <p> If there's still a path after applying all the quries print "-1". </p> <p> <b>NOTE</b> : There will always be a path initially i.e Answer lies between 1 and Q always (both inclusive) or is -1 </p>
<p>First line comprises <b>N</b>- the dimension of the square field.</p> <p> Next N lines each have N numbers that represent the field as stated above.</p> <p>Next line has an integer <b>Q</b>, denoting the number of queries. </p> <p> Q lines follow. Each query will be of the form <b>"i j"</b> (without quotes) i.e <b>a blockage is added at the coordinates (i,j).</b> </p>
<p>Output an integer that denotes the query number from which it shall become impossible to cross the field. </p>
<p>Note : Indices are 0 based.</p> N<=1000<br/> Q<=100000<br/>