






from __future__ import annotations

lowerCamelCase : Optional[int]						   =       [
    [-1, 0],  # left
    [0, -1],  # down
    [1, 0],  # right
    [0, 1],  # up
]
def       snake_case_		(     lowerCAmelCase_       :						list[list[int]]       ,       lowerCAmelCase_       :						list[int]       ,       lowerCAmelCase_       :						list[int]       ,       lowerCAmelCase_       :						int       ,       lowerCAmelCase_       :						list[list[int]]       ,       ):
							__lowercase      :							str				=     [
							    [0 for col in range(len(grid[0]      )      )] for row in range(len(lowerCAmelCase_      )      )
							]  # the reference grid
							__lowercase      :							str				=     1
							__lowercase      :							Optional[Any]				=     [
							    [0 for col in range(len(grid[0]      )      )] for row in range(len(lowerCAmelCase_      )      )
							]  # the action grid

							__lowercase      :							Optional[Any]				=     init[0]
							__lowercase      :							Dict				=     init[1]
							__lowercase      :							str				=     0
							__lowercase      :							Union[str, Any]				=     g + heuristic[x][y]  # cost from starting cell to destination cell
							__lowercase      :							Any				=     [[f, g, x, y]]

							__lowercase      :							Union[str, Any]				=     False  # flag that is set when search is complete
							__lowercase      :							Optional[int]				=     False  # flag set if we can't find expand

							while not found and not resign:
														if len(lowerCAmelCase_      ) == 0:
																					raise ValueError("""Algorithm is unable to find solution"""      )
														else:  # to choose the least costliest action so as to move closer to the goal
																					cell.sort()
																					cell.reverse()
																					__lowercase      :							Tuple				=     cell.pop()
																					__lowercase      :							Optional[int]				=     next_cell[2]
																					__lowercase      :							Tuple				=     next_cell[3]
																					__lowercase      :							List[Any]				=     next_cell[1]

																					if x == goal[0] and y == goal[1]:
																												__lowercase      :							Optional[Any]				=     True
																					else:
																												for i in range(len(lowerCAmelCase_      )      ):  # to try out different valid actions
																																			__lowercase      :							Dict				=     x + DIRECTIONS[i][0]
																																			__lowercase      :							Any				=     y + DIRECTIONS[i][1]
																																			if xa >= 0 and xa < len(lowerCAmelCase_      ) and ya >= 0 and ya < len(grid[0]      ):
																																										if closed[xa][ya] == 0 and grid[xa][ya] == 0:
																																																	__lowercase      :							str				=     g + cost
																																																	__lowercase      :							Tuple				=     ga + heuristic[xa][ya]
																																																	cell.append([fa, ga, xa, ya]      )
																																																	__lowercase      :							List[Any]				=     1
																																																	__lowercase      :							List[str]				=     i
							__lowercase      :							int				=     []
							__lowercase      :							str				=     goal[0]
							__lowercase      :							Dict				=     goal[1]
							invpath.append([x, y]      )  # we get the reverse path from here
							while x != init[0] or y != init[1]:
														__lowercase      :							List[str]				=     x - DIRECTIONS[action[x][y]][0]
														__lowercase      :							int				=     y - DIRECTIONS[action[x][y]][1]
														__lowercase      :							int				=     xa
														__lowercase      :							int				=     ya
														invpath.append([x, y]      )

							__lowercase      :							List[Any]				=     []
							for i in range(len(lowerCAmelCase_      )      ):
														path.append(invpath[len(lowerCAmelCase_      ) - 1 - i]      )
							return path, action


if __name__ == "__main__":
	lowerCamelCase : Any						   =       [
	    [0, 1, 0, 0, 0, 0],
	    [0, 1, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
	    [0, 1, 0, 0, 0, 0],
	    [0, 1, 0, 0, 1, 0],
	    [0, 0, 0, 0, 1, 0],
	]

	lowerCamelCase : Any						   =       [0, 0]
	# all coordinates are given in format [y,x]
	lowerCamelCase : str						   =       [len(grid) - 1, len(grid[0]) - 1]
	lowerCamelCase : List[Any]						   =       1

	# the cost map which pushes the path closer to the goal
	lowerCamelCase : str						   =       [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			lowerCamelCase : Tuple						   =       abs(i - goal[0]) + abs(j - goal[1])
			if grid[i][j] == 1:
				# added extra penalty in the heuristic map
				lowerCamelCase : str						   =       99

	lowerCamelCase : Optional[Any]						   =       search(grid, init, goal, cost, heuristic)

	print('''ACTION MAP''')
	for i in range(len(action)):
		print(action[i])

	for i in range(len(path)):
		print(path[i])










import inspect
import unittest

from transformers import MobileNetVaConfig
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
	import torch

	from transformers import MobileNetVaForImageClassification, MobileNetVaForSemanticSegmentation, MobileNetVaModel
	from transformers.models.mobilenet_va.modeling_mobilenet_va import MOBILENET_V2_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
	from PIL import Image

	from transformers import MobileNetVaImageProcessor

class 		lowerCAmelCase     ( __a			):

					'''simple docstring'''

					def       lowerCAmelCase				(  self				:	List[str]							)			->  Optional[int]:


												"""simple docstring"""

												__lowercase      :							str				=     self.config_class(**self.inputs_dict							)
												self.parent.assertTrue(hasattr(__a		,     """tf_padding"""							)							)
												self.parent.assertTrue(hasattr(__a		,     """depth_multiplier"""							)							)







class 		lowerCAmelCase     :

					'''simple docstring'''

					def __init__(  self				:	Union[str, Any]		,     __a				:	Tuple		,     __a				:	str=13		,     __a				:	Dict=3		,     __a				:	List[Any]=32		,     __a				:	Any=0.25		,     __a				:	Any=8		,     __a				:	Optional[int]=8		,     __a				:	Optional[int]=6		,     __a				:	Dict=32		,     __a				:	Tuple=True		,     __a				:	List[Any]=True		,     __a				:	Optional[int]=True		,     __a				:	Tuple="relu6"		,     __a				:	Optional[Any]=1280		,     __a				:	str=0.1		,     __a				:	str=0.02		,     __a				:	Optional[Any]=True		,     __a				:	Tuple=True		,     __a				:	Dict=10		,     __a				:	Optional[Any]=None		,     )			->  Any:


												"""simple docstring"""

												__lowercase      :							List[str]				=     parent
												__lowercase      :							Tuple				=     batch_size
												__lowercase      :							Dict				=     num_channels
												__lowercase      :							Optional[int]				=     image_size
												__lowercase      :							int				=     depth_multiplier
												__lowercase      :							str				=     depth_divisible_by
												__lowercase      :							int				=     min_depth
												__lowercase      :							Tuple				=     expand_ratio
												__lowercase      :							Optional[int]				=     tf_padding
												__lowercase      :							Dict				=     output_stride
												__lowercase      :							Dict				=     first_layer_is_expansion
												__lowercase      :							Optional[Any]				=     finegrained_output
												__lowercase      :							str				=     hidden_act
												__lowercase      :							Union[str, Any]				=     last_hidden_size if finegrained_output else int(last_hidden_size * depth_multiplier							)
												__lowercase      :							Optional[int]				=     classifier_dropout_prob
												__lowercase      :							int				=     use_labels
												__lowercase      :							Optional[int]				=     is_training
												__lowercase      :							Dict				=     num_labels
												__lowercase      :							Tuple				=     initializer_range
												__lowercase      :							Optional[Any]				=     scope



					def       lowerCAmelCase				(  self				:	Any							)			->  Optional[Any]:


												"""simple docstring"""

												__lowercase      :							Tuple				=     floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]							)

												__lowercase      :							List[Any]				=     None
												__lowercase      :							Optional[Any]				=     None
												if self.use_labels:
																			__lowercase      :							List[Any]				=     ids_tensor([self.batch_size]		,     self.num_labels							)
																			__lowercase      :							Optional[int]				=     ids_tensor([self.batch_size, self.image_size, self.image_size]		,     self.num_labels							)

												__lowercase      :							List[Any]				=     self.get_config()

												return config, pixel_values, labels, pixel_labels



					def       lowerCAmelCase				(  self				:	str							)			->  Union[str, Any]:


												"""simple docstring"""

												return MobileNetVaConfig(
												    num_channels=self.num_channels		,     image_size=self.image_size		,     depth_multiplier=self.depth_multiplier		,     depth_divisible_by=self.depth_divisible_by		,     min_depth=self.min_depth		,     expand_ratio=self.expand_ratio		,     output_stride=self.output_stride		,     first_layer_is_expansion=self.first_layer_is_expansion		,     finegrained_output=self.finegrained_output		,     hidden_act=self.hidden_act		,     tf_padding=self.tf_padding		,     classifier_dropout_prob=self.classifier_dropout_prob		,     initializer_range=self.initializer_range		,     )



					def       lowerCAmelCase				(  self				:	Tuple		,     __a				:	Dict		,     __a				:	Tuple		,     __a				:	Optional[int]		,     __a				:	Union[str, Any]							)			->  List[Any]:


												"""simple docstring"""

												__lowercase      :							Optional[int]				=     MobileNetVaModel(config=__a							)
												model.to(__a							)
												model.eval()
												__lowercase      :							Tuple				=     model(__a							)
												self.parent.assertEqual(
												    result.last_hidden_state.shape		,     (
												        self.batch_size,
												        self.last_hidden_size,
												        self.image_size // self.output_stride,
												        self.image_size // self.output_stride,
												    )		,     )
												self.parent.assertEqual(
												    result.pooler_output.shape		,     (self.batch_size, self.last_hidden_size)		,     )



					def       lowerCAmelCase				(  self				:	List[str]		,     __a				:	Optional[int]		,     __a				:	List[str]		,     __a				:	str		,     __a				:	Optional[int]							)			->  Tuple:


												"""simple docstring"""

												__lowercase      :							List[Any]				=     self.num_labels
												__lowercase      :							Dict				=     MobileNetVaForImageClassification(__a							)
												model.to(__a							)
												model.eval()
												__lowercase      :							Dict				=     model(__a		,     labels=__a							)
												self.parent.assertEqual(result.logits.shape		,     (self.batch_size, self.num_labels)							)



					def       lowerCAmelCase				(  self				:	int		,     __a				:	List[str]		,     __a				:	Tuple		,     __a				:	Any		,     __a				:	List[str]							)			->  Optional[int]:


												"""simple docstring"""

												__lowercase      :							int				=     self.num_labels
												__lowercase      :							List[Any]				=     MobileNetVaForSemanticSegmentation(__a							)
												model.to(__a							)
												model.eval()
												__lowercase      :							Dict				=     model(__a							)
												self.parent.assertEqual(
												    result.logits.shape		,     (
												        self.batch_size,
												        self.num_labels,
												        self.image_size // self.output_stride,
												        self.image_size // self.output_stride,
												    )		,     )
												__lowercase      :							str				=     model(__a		,     labels=__a							)
												self.parent.assertEqual(
												    result.logits.shape		,     (
												        self.batch_size,
												        self.num_labels,
												        self.image_size // self.output_stride,
												        self.image_size // self.output_stride,
												    )		,     )



					def       lowerCAmelCase				(  self				:	Tuple							)			->  Optional[int]:


												"""simple docstring"""

												__lowercase      :							List[str]				=     self.prepare_config_and_inputs()
												__lowercase			,			__lowercase			,			__lowercase			,			__lowercase      :							List[str]				=     config_and_inputs
												__lowercase      :							List[Any]				=     {"""pixel_values""": pixel_values}
												return config, inputs_dict







@require_torch
class 		lowerCAmelCase     ( __a      ,       __a      ,       unittest.TestCase			):

					'''simple docstring'''

					_A						:			Tuple									=      (
					    (MobileNetVaModel, MobileNetVaForImageClassification, MobileNetVaForSemanticSegmentation)
					    if is_torch_available()
					    else ()
					)
					_A						:			Optional[Any]									=      (
					    {
					        '''feature-extraction''': MobileNetVaModel,
					        '''image-classification''': MobileNetVaForImageClassification,
					        '''image-segmentation''': MobileNetVaForSemanticSegmentation,
					    }
					    if is_torch_available()
					    else {}
					)

					_A						:			Tuple									=      False
					_A						:			List[str]									=      False
					_A						:			List[str]									=      False
					_A						:			Optional[int]									=      False



					def       lowerCAmelCase				(  self				:	Optional[Any]							)			->  List[Any]:


												"""simple docstring"""

												__lowercase      :							Union[str, Any]				=     MobileNetVaModelTester(self							)
												__lowercase      :							int				=     MobileNetVaConfigTester(self		,     config_class=__a		,     has_text_modality=__a							)



					def       lowerCAmelCase				(  self				:	Union[str, Any]							)			->  List[Any]:


												"""simple docstring"""

												self.config_tester.run_common_tests()



					@unittest.skip(reason="""MobileNetV2 does not use inputs_embeds"""							)
					def       lowerCAmelCase				(  self				:	List[str]							)			->  Union[str, Any]:


												"""simple docstring"""

												pass



					@unittest.skip(reason="""MobileNetV2 does not support input and output embeddings"""							)
					def       lowerCAmelCase				(  self				:	Any							)			->  Tuple:


												"""simple docstring"""

												pass



					@unittest.skip(reason="""MobileNetV2 does not output attentions"""							)
					def       lowerCAmelCase				(  self				:	List[str]							)			->  int:


												"""simple docstring"""

												pass



					def       lowerCAmelCase				(  self				:	List[str]							)			->  Dict:


												"""simple docstring"""

												__lowercase			,			__lowercase      :							Optional[int]				=     self.model_tester.prepare_config_and_inputs_for_common()

												for model_class in self.all_model_classes:
																			__lowercase      :							List[Any]				=     model_class(__a							)
																			__lowercase      :							Any				=     inspect.signature(model.forward							)
																			# signature.parameters is an OrderedDict => so arg_names order is deterministic
																			__lowercase      :							int				=     [*signature.parameters.keys()]

																			__lowercase      :							Any				=     ["""pixel_values"""]
																			self.assertListEqual(arg_names[:1]		,     __a							)



					def       lowerCAmelCase				(  self				:	Dict							)			->  Any:


												"""simple docstring"""

												__lowercase      :							Union[str, Any]				=     self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_model(*__a							)



					def       lowerCAmelCase				(  self				:	List[str]							)			->  Tuple:


												"""simple docstring"""

												def check_hidden_states_output(__a				:	List[Any]		,     __a				:	Tuple		,     __a				:	List[str]							):
																			__lowercase      :							Optional[Any]				=     model_class(__a							)
																			model.to(__a							)
																			model.eval()

																			with torch.no_grad():
																										__lowercase      :							List[Any]				=     model(**self._prepare_for_class(__a		,     __a							)							)

																			__lowercase      :							Tuple				=     outputs.hidden_states

																			__lowercase      :							str				=     16
																			self.assertEqual(len(__a							)		,     __a							)

												__lowercase			,			__lowercase      :							int				=     self.model_tester.prepare_config_and_inputs_for_common()

												for model_class in self.all_model_classes:
																			__lowercase      :							Any				=     True
																			check_hidden_states_output(__a		,     __a		,     __a							)

																			# check that output_hidden_states also work using config
																			del inputs_dict["output_hidden_states"]
																			__lowercase      :							Union[str, Any]				=     True

																			check_hidden_states_output(__a		,     __a		,     __a							)



					def       lowerCAmelCase				(  self				:	Union[str, Any]							)			->  Any:


												"""simple docstring"""

												__lowercase      :							Dict				=     self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_for_image_classification(*__a							)



					def       lowerCAmelCase				(  self				:	List[str]							)			->  int:


												"""simple docstring"""

												__lowercase      :							Union[str, Any]				=     self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_for_semantic_segmentation(*__a							)



					@slow
					def       lowerCAmelCase				(  self				:	Optional[int]							)			->  Optional[Any]:


												"""simple docstring"""

												for model_name in MOBILENET_V2_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																			__lowercase      :							Optional[int]				=     MobileNetVaModel.from_pretrained(__a							)
																			self.assertIsNotNone(__a							)







def       snake_case_		(     ):
							__lowercase      :							List[Any]				=     Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png"""      )
							return image



@require_torch
@require_vision
class 		lowerCAmelCase     ( unittest.TestCase			):

					'''simple docstring'''

					@cached_property
					def       lowerCAmelCase				(  self				:	Any							)			->  Union[str, Any]:


												"""simple docstring"""

												return (
												    MobileNetVaImageProcessor.from_pretrained("""google/mobilenet_v2_1.0_224"""							) if is_vision_available() else None
												)



					@slow
					def       lowerCAmelCase				(  self				:	str							)			->  int:


												"""simple docstring"""

												__lowercase      :							Tuple				=     MobileNetVaForImageClassification.from_pretrained("""google/mobilenet_v2_1.0_224"""							).to(__a							)

												__lowercase      :							str				=     self.default_image_processor
												__lowercase      :							Tuple				=     prepare_img()
												__lowercase      :							Tuple				=     image_processor(images=__a		,     return_tensors="""pt"""							).to(__a							)

												# forward pass
												with torch.no_grad():
																			__lowercase      :							str				=     model(**__a							)

												# verify the logits
												__lowercase      :							Union[str, Any]				=     torch.Size((1, 1001)							)
												self.assertEqual(outputs.logits.shape		,     __a							)

												__lowercase      :							str				=     torch.tensor([0.2445, -1.1993, 0.1905]							).to(__a							)

												self.assertTrue(torch.allclose(outputs.logits[0, :3]		,     __a		,     atol=1E-4							)							)



					@slow
					def       lowerCAmelCase				(  self				:	Tuple							)			->  Any:


												"""simple docstring"""

												__lowercase      :							int				=     MobileNetVaForSemanticSegmentation.from_pretrained("""google/deeplabv3_mobilenet_v2_1.0_513"""							)
												__lowercase      :							Dict				=     model.to(__a							)

												__lowercase      :							Tuple				=     MobileNetVaImageProcessor.from_pretrained("""google/deeplabv3_mobilenet_v2_1.0_513"""							)

												__lowercase      :							List[str]				=     prepare_img()
												__lowercase      :							Optional[int]				=     image_processor(images=__a		,     return_tensors="""pt"""							).to(__a							)

												# forward pass
												with torch.no_grad():
																			__lowercase      :							Union[str, Any]				=     model(**__a							)
												__lowercase      :							Any				=     outputs.logits

												# verify the logits
												__lowercase      :							Dict				=     torch.Size((1, 21, 65, 65)							)
												self.assertEqual(logits.shape		,     __a							)

												__lowercase      :							str				=     torch.tensor(
												    [
												        [[17.5790, 17.7581, 18.3355], [18.3257, 18.4230, 18.8973], [18.6169, 18.8650, 19.2187]],
												        [[-2.1595, -2.0977, -2.3741], [-2.4226, -2.3028, -2.6835], [-2.7819, -2.5991, -2.7706]],
												        [[4.2058, 4.8317, 4.7638], [4.4136, 5.0361, 4.9383], [4.5028, 4.9644, 4.8734]],
												    ]		,     device=__a		,     )

												self.assertTrue(torch.allclose(logits[0, :3, :3, :3]		,     __a		,     atol=1E-4							)							)