
from __future__ import annotations

import time

__snake_case								=  list[tuple[int, int]]

__snake_case								=  [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

__snake_case								=  [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right




class 						lowercase__  :
	def __init__(			self							:   List[Any]       ,   UpperCAmelCase_							:   int       ,   UpperCAmelCase_							:   int       ,   UpperCAmelCase_							:   int       ,   UpperCAmelCase_							:   int       ,   UpperCAmelCase_							:   Node | None							):
						SCREAMING_SNAKE_CASE__													= pos_x
						SCREAMING_SNAKE_CASE__													= pos_y
						SCREAMING_SNAKE_CASE__													= (pos_y, pos_x)
						SCREAMING_SNAKE_CASE__													= goal_x
						SCREAMING_SNAKE_CASE__													= goal_y
						SCREAMING_SNAKE_CASE__													= parent





class 						lowercase__  :
	def __init__(			self							:   Any       ,   UpperCAmelCase_							:   tuple[int, int]       ,   UpperCAmelCase_							:   tuple[int, int]							):
						SCREAMING_SNAKE_CASE__													= Node(start[1]       ,   start[0]       ,   goal[1]       ,   goal[0]       ,   UpperCAmelCase_							)
						SCREAMING_SNAKE_CASE__													= Node(goal[1]       ,   goal[0]       ,   goal[1]       ,   goal[0]       ,   UpperCAmelCase_							)

						SCREAMING_SNAKE_CASE__													= [self.start]
						SCREAMING_SNAKE_CASE__													= False
	def      A_				(			self							:   Union[str, Any]							):
						while self.node_queue:
											SCREAMING_SNAKE_CASE__													= self.node_queue.pop(0							)

											if current_node.pos == self.target.pos:
																SCREAMING_SNAKE_CASE__													= True
																return self.retrace_path(UpperCAmelCase_							)

											SCREAMING_SNAKE_CASE__													= self.get_successors(UpperCAmelCase_							)

											for node in successors:
																self.node_queue.append(UpperCAmelCase_							)

						if not self.reached:
											return [self.start.pos]
						return None
	def      A_				(			self							:   Any       ,   UpperCAmelCase_							:   Node							):
						SCREAMING_SNAKE_CASE__													= []
						for action in delta:
											SCREAMING_SNAKE_CASE__													= parent.pos_x + action[1]
											SCREAMING_SNAKE_CASE__													= parent.pos_y + action[0]
											if not (0 <= pos_x <= len(grid[0]							) - 1 and 0 <= pos_y <= len(UpperCAmelCase_							) - 1):
																continue

											if grid[pos_y][pos_x] != 0:
																continue

											successors.append(
											    Node(UpperCAmelCase_       ,   UpperCAmelCase_       ,   self.target.pos_y       ,   self.target.pos_x       ,   UpperCAmelCase_							)							)
						return successors





	def      A_				(			self							:   Optional[int]       ,   UpperCAmelCase_							:   Node | None							):
						SCREAMING_SNAKE_CASE__													= node
						SCREAMING_SNAKE_CASE__													= []
						while current_node is not None:
											path.append((current_node.pos_y, current_node.pos_x)							)
											SCREAMING_SNAKE_CASE__													= current_node.parent
						path.reverse()
						return path





class 						lowercase__  :
	def __init__(			self							:   Union[str, Any]       ,   UpperCAmelCase_							:   Any       ,   UpperCAmelCase_							:   Union[str, Any]							):
						SCREAMING_SNAKE_CASE__													= BreadthFirstSearch(UpperCAmelCase_       ,   UpperCAmelCase_							)
						SCREAMING_SNAKE_CASE__													= BreadthFirstSearch(UpperCAmelCase_       ,   UpperCAmelCase_							)
						SCREAMING_SNAKE_CASE__													= False
	def      A_				(			self							:   Union[str, Any]							):
						while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
											SCREAMING_SNAKE_CASE__													= self.fwd_bfs.node_queue.pop(0							)
											SCREAMING_SNAKE_CASE__													= self.bwd_bfs.node_queue.pop(0							)

											if current_bwd_node.pos == current_fwd_node.pos:
																SCREAMING_SNAKE_CASE__													= True
																return self.retrace_bidirectional_path(
																    UpperCAmelCase_       ,   UpperCAmelCase_							)

											SCREAMING_SNAKE_CASE__													= current_bwd_node
											SCREAMING_SNAKE_CASE__													= current_fwd_node

											SCREAMING_SNAKE_CASE__													= {
											    self.fwd_bfs: self.fwd_bfs.get_successors(UpperCAmelCase_							),
											    self.bwd_bfs: self.bwd_bfs.get_successors(UpperCAmelCase_							),
											}

											for bfs in [self.fwd_bfs, self.bwd_bfs]:
																for node in successors[bfs]:
																					bfs.node_queue.append(UpperCAmelCase_							)

						if not self.reached:
											return [self.fwd_bfs.start.pos]
						return None





	def      A_				(			self							:   Dict       ,   UpperCAmelCase_							:   Node       ,   UpperCAmelCase_							:   Node							):
						SCREAMING_SNAKE_CASE__													= self.fwd_bfs.retrace_path(UpperCAmelCase_							)
						SCREAMING_SNAKE_CASE__													= self.bwd_bfs.retrace_path(UpperCAmelCase_							)
						bwd_path.pop()
						bwd_path.reverse()
						SCREAMING_SNAKE_CASE__													= fwd_path + bwd_path
						return path


if __name__ == "__main__":
				# all coordinates are given in format [y,x]
				import doctest

				doctest.testmod()
				__snake_case								=  (0, 0)
				__snake_case								=  (len(grid) - 1, len(grid[0]) - 1)
				for elem in grid:
								print(elem)

				__snake_case								=  time.time()
				__snake_case								=  BreadthFirstSearch(init, goal)
				__snake_case								=  bfs.search()
				__snake_case								=  time.time() - start_bfs_time

				print("""Unidirectional BFS computation time : """, bfs_time)

				__snake_case								=  time.time()
				__snake_case								=  BidirectionalBreadthFirstSearch(init, goal)
				__snake_case								=  bd_bfs.search()
				__snake_case								=  time.time() - start_bd_bfs_time

				print("""Bidirectional BFS computation time : """, bd_bfs_time)







def 							_lowercase							(     UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)		->		int:
					'''simple docstring'''


					def update_area_of_max_square(UpperCamelCase_	,	UpperCamelCase_		) -> int:
										# BASE CASE
										if row >= rows or col >= cols:
															return 0

										SCREAMING_SNAKE_CASE__													= update_area_of_max_square(UpperCamelCase_	,	col + 1		)
										SCREAMING_SNAKE_CASE__													= update_area_of_max_square(row + 1	,	col + 1		)
										SCREAMING_SNAKE_CASE__													= update_area_of_max_square(row + 1	,	UpperCamelCase_		)

										if mat[row][col]:
															SCREAMING_SNAKE_CASE__													= 1 + min([right, diagonal, down]		)
															SCREAMING_SNAKE_CASE__													= max(largest_square_area[0]	,	UpperCamelCase_		)
															return sub_problem_sol
										else:
															return 0

					SCREAMING_SNAKE_CASE__													= [0]
					update_area_of_max_square(0	,	0		)
					return largest_square_area[0]






def 							_lowercase							(     UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)		->		int:
					'''simple docstring'''


					def update_area_of_max_square_using_dp_array(
					    UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		) -> int:
										if row >= rows or col >= cols:
															return 0
										if dp_array[row][col] != -1:
															return dp_array[row][col]

										SCREAMING_SNAKE_CASE__													= update_area_of_max_square_using_dp_array(UpperCamelCase_	,	col + 1	,	UpperCamelCase_		)
										SCREAMING_SNAKE_CASE__													= update_area_of_max_square_using_dp_array(row + 1	,	col + 1	,	UpperCamelCase_		)
										SCREAMING_SNAKE_CASE__													= update_area_of_max_square_using_dp_array(row + 1	,	UpperCamelCase_	,	UpperCamelCase_		)

										if mat[row][col]:
															SCREAMING_SNAKE_CASE__													= 1 + min([right, diagonal, down]		)
															SCREAMING_SNAKE_CASE__													= max(largest_square_area[0]	,	UpperCamelCase_		)
															SCREAMING_SNAKE_CASE__													= sub_problem_sol
															return sub_problem_sol
										else:
															return 0

					SCREAMING_SNAKE_CASE__													= [0]
					SCREAMING_SNAKE_CASE__													= [[-1] * cols for _ in range(UpperCamelCase_		)]
					update_area_of_max_square_using_dp_array(0	,	0	,	UpperCamelCase_		)

					return largest_square_area[0]






def 							_lowercase							(     UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)		->		int:
					'''simple docstring'''


					SCREAMING_SNAKE_CASE__													= [[0] * (cols + 1) for _ in range(rows + 1		)]
					SCREAMING_SNAKE_CASE__													= 0
					for row in range(rows - 1	,	-1	,	-1		):
										for col in range(cols - 1	,	-1	,	-1		):
															SCREAMING_SNAKE_CASE__													= dp_array[row][col + 1]
															SCREAMING_SNAKE_CASE__													= dp_array[row + 1][col + 1]
															SCREAMING_SNAKE_CASE__													= dp_array[row + 1][col]

															if mat[row][col] == 1:
																				SCREAMING_SNAKE_CASE__													= 1 + min(UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)
																				SCREAMING_SNAKE_CASE__													= max(dp_array[row][col]	,	UpperCamelCase_		)
															else:
																				SCREAMING_SNAKE_CASE__													= 0

					return largest_square_area






def 							_lowercase							(     UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)		->		int:
					'''simple docstring'''


					SCREAMING_SNAKE_CASE__													= [0] * (cols + 1)
					SCREAMING_SNAKE_CASE__													= [0] * (cols + 1)
					SCREAMING_SNAKE_CASE__													= 0
					for row in range(rows - 1	,	-1	,	-1		):
										for col in range(cols - 1	,	-1	,	-1		):
															SCREAMING_SNAKE_CASE__													= current_row[col + 1]
															SCREAMING_SNAKE_CASE__													= next_row[col + 1]
															SCREAMING_SNAKE_CASE__													= next_row[col]

															if mat[row][col] == 1:
																				SCREAMING_SNAKE_CASE__													= 1 + min(UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)
																				SCREAMING_SNAKE_CASE__													= max(current_row[col]	,	UpperCamelCase_		)
															else:
																				SCREAMING_SNAKE_CASE__													= 0
										SCREAMING_SNAKE_CASE__													= current_row

					return largest_square_area


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				print(largest_square_area_in_matrix_bottom_up(2, 2, [[1, 1], [1, 1]]))





