fork download
copy 
  1. t = int(input())
  2. while t > 0:
  3. 	N=int(input())
  4. 	grid=[[int(x) for x in input().split()] for _ in range(N)]
  5.  
  6. 	class Node:
  7. 	    def __init__(self,prev,next,x,y):
  8. 	        self.prev=prev
  9. 	        self.next=next
  10. 	        self.x=x
  11. 	        self.y=y
  12.  
  13. 	rear=None
  14. 	front=None
  15.  
  16. 	for i in range(len(grid)):
  17. 	    for j in range(len(grid[0])):
  18. 	        if grid[i][j] == 1:
  19. 	            if rear == None:
  20. 	                new=Node(None,None,i,j)
  21. 	                front = new
  22. 	                rear = new
  23. 	            else:
  24. 	                new=Node(rear,None,i,j)
  25. 	                rear.next=new
  26. 	                rear=new
  27. 	stop=rear
  28. 	count=0
  29. 	while front != None:
  30. 	    x,y=front.x,front.y
  31. 	    if y+1 < N:
  32. 	        if grid[x][y+1] == 0:
  33. 	            grid[x][y+1]=1
  34. 	            new=Node(rear,None,x,y+1)
  35. 	            rear.next=new
  36. 	            rear=new
  37. 	        if grid[x][y+1] == 2:
  38. 	            break
  39. 	    if y > 0:
  40. 	        if grid[x][y-1] == 0:
  41. 	            grid[x][y-1]=1
  42. 	            new=Node(rear,None,x,y-1)
  43. 	            rear.next=new
  44. 	            rear=new
  45. 	        if grid[x][y-1] == 2:
  46. 	            break
  47.  
  48. 	    if x+1 < N:
  49. 	        if grid[x+1][y] == 0:
  50. 	            grid[x+1][y]=1
  51. 	            new=Node(rear,None,x+1,y)
  52. 	            rear.next=new
  53. 	            rear=new
  54. 	        if grid[x+1][y] == 2:
  55. 	            break
  56. 	    if x > 0:
  57. 	        if grid[x-1][y] == 0:
  58. 	            grid[x-1][y]=1
  59. 	            new=Node(rear,None,x-1,y)
  60. 	            rear.next=new
  61. 	            rear=new
  62. 	        if grid[x-1][y]==2:
  63. 	            break
  64. 	    if front == stop and front != rear:
  65. 	        count+=1
  66. 	        stop=rear
  67. 	    front=front.next
  68. 	print(count+1)
  69. 	t = t - 1
Success #stdin #stdout 0.02s 9232KB
comments (?)
stdin
copy 
1
3
0 0 1
2 0 1
0 0 0
stdout
copy 
2
https://ideone.com/UIhjCO
language:
Python 3 (python  3.12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!