




'''simple docstring'''


def 	snake_case_					():





							'''simple docstring'''


							return [list(range(1000 - i				,		-1000 - i				,		-1   )   ) for i in range(1000   )]


_snake_case   :   Any     							=	generate_large_matrix()
_snake_case   :   Optional[int]     							=	(
    [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]],
    [[3, 2], [1, 0]],
    [[7, 7, 6]],
    [[7, 7, 6], [-1, -2, -3]],
    grid,
)
def 	snake_case_					(UpperCamelCase :						list[list[int]]   ):





							'''simple docstring'''


							assert all(row == sorted(_lowercase				,		reverse=_lowercase   ) for row in grid   )
							assert all(list(_lowercase   ) == sorted(_lowercase				,		reverse=_lowercase   ) for col in zip(*_lowercase   )   )
def 	snake_case_					(UpperCamelCase :						list[int]   ):





							'''simple docstring'''


							_a			  =       0
							_a			  =       len(_lowercase   ) - 1

							# Edge cases such as no values or all numbers are negative.
							if not array or array[0] < 0:
														return 0

							while right + 1 > left:
														_a			  =       (left + right) // 2
														_a			  =       array[mid]

														# Num must be negative and the index must be greater than or equal to 0.
														if num < 0 and array[mid - 1] >= 0:
																					return mid

														if num >= 0:
																					_a			  =       mid + 1
														else:
																					_a			  =       mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
							return len(_lowercase   )
def 	snake_case_					(UpperCamelCase :						list[list[int]]   ):





							'''simple docstring'''


							_a			  =       0
							_a			  =       len(grid[0]   )

							for i in range(len(_lowercase   )   ):
														_a			  =       find_negative_index(grid[i][:bound]   )
														total += bound
							return (len(_lowercase   ) * len(grid[0]   )) - total
def 	snake_case_					(UpperCamelCase :						list[list[int]]   ):





							'''simple docstring'''


							return len([number for row in grid for number in row if number < 0]   )
def 	snake_case_					(UpperCamelCase :						list[list[int]]   ):





							'''simple docstring'''


							_a			  =       0
							for row in grid:
														for i, number in enumerate(_lowercase   ):
																					if number < 0:
																												total += len(_lowercase   ) - i
																												break
							return total
def 	snake_case_					():





							'''simple docstring'''


							from timeit import timeit

							print('''Running benchmarks'''   )
							_a			  =       (
							    "from __main__ import count_negatives_binary_search, "
							    "count_negatives_brute_force, count_negatives_brute_force_with_break, grid"
							)
							for func in (
							    "count_negatives_binary_search",  # took 0.7727 seconds
							    "count_negatives_brute_force_with_break",  # took 4.6505 seconds
							    "count_negatives_brute_force",  # took 12.8160 seconds
							):
														_a			  =       timeit(f'{func}(grid=grid)'				,		setup=_lowercase				,		number=500   )
														print(f'{func}() took {time:0.4f} seconds'   )


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				benchmark()







'''simple docstring'''


_snake_case   :   Any     							=	{
    'A': ['B', 'C', 'E'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['A', 'B', 'D'],
    'F': ['C'],
    'G': ['C'],
}
def 	snake_case_					(UpperCamelCase :						dict				,		UpperCamelCase :						Dict				,		UpperCamelCase :						Optional[int]   ):





							'''simple docstring'''


							_a			  =       set()
							# keep track of all the paths to be checked
							_a			  =       [[start]]

							# return path if start is goal
							if start == goal:
														return [start]

							# keeps looping until all possible paths have been checked
							while queue:
														# pop the first path from the queue
														_a			  =       queue.pop(0   )
														# get the last node from the path
														_a			  =       path[-1]
														if node not in explored:
																					_a			  =       graph[node]
																					# go through all neighbour nodes, construct a new path and
																					# push it into the queue
																					for neighbour in neighbours:
																												_a			  =       list(UpperCamelCase   )
																												new_path.append(UpperCamelCase   )
																												queue.append(UpperCamelCase   )
																												# return path if neighbour is goal
																												if neighbour == goal:
																																			return new_path

            # mark node as explored
																					explored.add(UpperCamelCase   )

    # in case there's no path between the 2 nodes
							return []
def 	snake_case_					(UpperCamelCase :						dict				,		UpperCamelCase :						Optional[int]				,		UpperCamelCase :						Dict   ):





							'''simple docstring'''


							if not graph or start not in graph or target not in graph:
														return -1
							if start == target:
														return 0
							_a			  =       [start]
							_a			  =       set(UpperCamelCase   )
							# Keep tab on distances from `start` node.
							_a			  =       {start: 0, target: -1}
							while queue:
														_a			  =       queue.pop(0   )
														if node == target:
																					_a			  =       (
																					    dist[node] if dist[target] == -1 else min(dist[target]				,		dist[node]   )
																					)
														for adjacent in graph[node]:
																					if adjacent not in visited:
																												visited.add(UpperCamelCase   )
																												queue.append(UpperCamelCase   )
																												_a			  =       dist[node] + 1
							return dist[target]


if __name__ == "__main__":
				print(bfs_shortest_path(demo_graph, 'G', 'D'))  # returns ['G', 'C', 'A', 'B', 'D']
				print(bfs_shortest_path_distance(demo_graph, 'G', 'D'))  # returns 4

