'''simple docstring'''







import unittest

import numpy as np

from transformers.testing_utils import require_pytesseract, require_torch
from transformers.utils import is_pytesseract_available, is_torch_available

from ...test_image_processing_common import ImageProcessingSavingTestMixin, prepare_image_inputs


if is_torch_available():
		import torch

if is_pytesseract_available():
		from PIL import Image

		from transformers import LayoutLMvaImageProcessor




class _SCREAMING_SNAKE_CASE(							unittest.TestCase					):




						def __init__(    self :       int							,							UpperCamelCase_ :       Optional[Any]							,							UpperCamelCase_ :       Optional[Any]=7							,							UpperCamelCase_ :       List[Any]=3							,							UpperCamelCase_ :       Tuple=18							,							UpperCamelCase_ :       Tuple=30							,							UpperCamelCase_ :       Any=4_00							,							UpperCamelCase_ :       List[Any]=True							,							UpperCamelCase_ :       Optional[int]=None							,							UpperCamelCase_ :       str=True							,							)     ->				Union[str, Any]:
													SCREAMING_SNAKE_CASE__     :str						    = size if size is not None else {'height': 18, 'width': 18}
													SCREAMING_SNAKE_CASE__     :Union[str, Any]						    = parent
													SCREAMING_SNAKE_CASE__     :Tuple						    = batch_size
													SCREAMING_SNAKE_CASE__     :Optional[Any]						    = num_channels
													SCREAMING_SNAKE_CASE__     :Tuple						    = image_size
													SCREAMING_SNAKE_CASE__     :Optional[int]						    = min_resolution
													SCREAMING_SNAKE_CASE__     :Any						    = max_resolution
													SCREAMING_SNAKE_CASE__     :List[str]						    = do_resize
													SCREAMING_SNAKE_CASE__     :Dict						    = size
													SCREAMING_SNAKE_CASE__     :int						    = apply_ocr




						def      __lowerCamelCase       (    self :       List[str]      )     ->				List[Any]:
													return {"do_resize": self.do_resize, "size": self.size, "apply_ocr": self.apply_ocr}




@require_torch
@require_pytesseract
class _SCREAMING_SNAKE_CASE(							_SCREAMING_SNAKE_CASE						,						unittest.TestCase					):
						A_			:							Tuple     		= LayoutLMvaImageProcessor if is_pytesseract_available() else None




						def      __lowerCamelCase       (    self :       List[Any]      )     ->				Optional[Any]:
													SCREAMING_SNAKE_CASE__     :Optional[Any]						    = LayoutLMvaImageProcessingTester(self      )




						@property
						def      __lowerCamelCase       (    self :       str      )     ->				Any:
													return self.image_processor_tester.prepare_image_processor_dict()




						def      __lowerCamelCase       (    self :       List[str]      )     ->				str:
													SCREAMING_SNAKE_CASE__     :Union[str, Any]						    = self.image_processing_class(**self.image_processor_dict      )
													self.assertTrue(hasattr(UpperCamelCase_							,							'do_resize'      )      )
													self.assertTrue(hasattr(UpperCamelCase_							,							'size'      )      )
													self.assertTrue(hasattr(UpperCamelCase_							,							'apply_ocr'      )      )




						def      __lowerCamelCase       (    self :       Optional[int]      )     ->				Tuple:
													SCREAMING_SNAKE_CASE__     :str						    = self.image_processing_class.from_dict(self.image_processor_dict      )
													self.assertEqual(image_processor.size							,							{'height': 18, 'width': 18}      )

													SCREAMING_SNAKE_CASE__     :List[Any]						    = self.image_processing_class.from_dict(self.image_processor_dict							,							size=42      )
													self.assertEqual(image_processor.size							,							{'height': 42, 'width': 42}      )




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




						def      __lowerCamelCase       (    self :       str      )     ->				int:
													# Initialize image_processing
													SCREAMING_SNAKE_CASE__     :Any						    = self.image_processing_class(**self.image_processor_dict      )
													# create random PIL images
													SCREAMING_SNAKE_CASE__     :Optional[int]						    = prepare_image_inputs(self.image_processor_tester							,							equal_resolution=UpperCamelCase_      )
													for image in image_inputs:
																				self.assertIsInstance(UpperCamelCase_							,							Image.Image      )

													# Test not batched input
													SCREAMING_SNAKE_CASE__     :str						    = image_processing(image_inputs[0]							,							return_tensors='pt'      )
													self.assertEqual(
													    encoding.pixel_values.shape							,							(
													        1,
													        self.image_processor_tester.num_channels,
													        self.image_processor_tester.size['height'],
													        self.image_processor_tester.size['width'],
													    )							,							)

													self.assertIsInstance(encoding.words							,							UpperCamelCase_      )
													self.assertIsInstance(encoding.boxes							,							UpperCamelCase_      )

													# Test batched
													SCREAMING_SNAKE_CASE__     :Optional[int]						    = image_processing(UpperCamelCase_							,							return_tensors='pt'      ).pixel_values
													self.assertEqual(
													    encoded_images.shape							,							(
													        self.image_processor_tester.batch_size,
													        self.image_processor_tester.num_channels,
													        self.image_processor_tester.size['height'],
													        self.image_processor_tester.size['width'],
													    )							,							)




						def      __lowerCamelCase       (    self :       Tuple      )     ->				Optional[Any]:
													# Initialize image_processing
													SCREAMING_SNAKE_CASE__     :Tuple						    = self.image_processing_class(**self.image_processor_dict      )
													# create random numpy tensors
													SCREAMING_SNAKE_CASE__     :Dict						    = prepare_image_inputs(self.image_processor_tester							,							equal_resolution=UpperCamelCase_							,							numpify=UpperCamelCase_      )
													for image in image_inputs:
																				self.assertIsInstance(UpperCamelCase_							,							np.ndarray      )

													# Test not batched input
													SCREAMING_SNAKE_CASE__     :Dict						    = image_processing(image_inputs[0]							,							return_tensors='pt'      ).pixel_values
													self.assertEqual(
													    encoded_images.shape							,							(
													        1,
													        self.image_processor_tester.num_channels,
													        self.image_processor_tester.size['height'],
													        self.image_processor_tester.size['width'],
													    )							,							)

													# Test batched
													SCREAMING_SNAKE_CASE__     :Any						    = image_processing(UpperCamelCase_							,							return_tensors='pt'      ).pixel_values
													self.assertEqual(
													    encoded_images.shape							,							(
													        self.image_processor_tester.batch_size,
													        self.image_processor_tester.num_channels,
													        self.image_processor_tester.size['height'],
													        self.image_processor_tester.size['width'],
													    )							,							)




						def      __lowerCamelCase       (    self :       Any      )     ->				Union[str, Any]:
													# Initialize image_processing
													SCREAMING_SNAKE_CASE__     :Dict						    = self.image_processing_class(**self.image_processor_dict      )
													# create random PyTorch tensors
													SCREAMING_SNAKE_CASE__     :Optional[int]						    = prepare_image_inputs(self.image_processor_tester							,							equal_resolution=UpperCamelCase_							,							torchify=UpperCamelCase_      )
													for image in image_inputs:
																				self.assertIsInstance(UpperCamelCase_							,							torch.Tensor      )

													# Test not batched input
													SCREAMING_SNAKE_CASE__     :Tuple						    = image_processing(image_inputs[0]							,							return_tensors='pt'      ).pixel_values
													self.assertEqual(
													    encoded_images.shape							,							(
													        1,
													        self.image_processor_tester.num_channels,
													        self.image_processor_tester.size['height'],
													        self.image_processor_tester.size['width'],
													    )							,							)

													# Test batched
													SCREAMING_SNAKE_CASE__     :Union[str, Any]						    = image_processing(UpperCamelCase_							,							return_tensors='pt'      ).pixel_values
													self.assertEqual(
													    encoded_images.shape							,							(
													        self.image_processor_tester.batch_size,
													        self.image_processor_tester.num_channels,
													        self.image_processor_tester.size['height'],
													        self.image_processor_tester.size['width'],
													    )							,							)




						def      __lowerCamelCase       (    self :       Union[str, Any]      )     ->				Union[str, Any]:
													# with apply_OCR = True
													SCREAMING_SNAKE_CASE__     :List[Any]						    = LayoutLMvaImageProcessor()

													from datasets import load_dataset

													SCREAMING_SNAKE_CASE__     :Any						    = load_dataset('hf-internal-testing/fixtures_docvqa'							,							split='test'      )

													SCREAMING_SNAKE_CASE__     :int						    = Image.open(ds[0]['file']      ).convert('RGB'      )

													SCREAMING_SNAKE_CASE__     :Tuple						    = image_processing(UpperCamelCase_							,							return_tensors='pt'      )

													self.assertEqual(encoding.pixel_values.shape							,							(1, 3, 2_24, 2_24)      )
													self.assertEqual(len(encoding.words      )							,							len(encoding.boxes      )      )

													# fmt: off
													# the words and boxes were obtained with Tesseract 4.1.1
													SCREAMING_SNAKE_CASE__     :List[Any]						    = [['11:14', 'to', '11:39', 'a.m', '11:39', 'to', '11:44', 'a.m.', '11:44', 'a.m.', 'to', '12:25', 'p.m.', '12:25', 'to', '12:58', 'p.m.', '12:58', 'to', '4:00', 'p.m.', '2:00', 'to', '5:00', 'p.m.', 'Coffee', 'Break', 'Coffee', 'will', 'be', 'served', 'for', 'men', 'and', 'women', 'in', 'the', 'lobby', 'adjacent', 'to', 'exhibit', 'area.', 'Please', 'move', 'into', 'exhibit', 'area.', '(Exhibits', 'Open)', 'TRRF', 'GENERAL', 'SESSION', '(PART', '|)', 'Presiding:', 'Lee', 'A.', 'Waller', 'TRRF', 'Vice', 'President', '“Introductory', 'Remarks”', 'Lee', 'A.', 'Waller,', 'TRRF', 'Vice', 'Presi-', 'dent', 'Individual', 'Interviews', 'with', 'TRRF', 'Public', 'Board', 'Members', 'and', 'Sci-', 'entific', 'Advisory', 'Council', 'Mem-', 'bers', 'Conducted', 'by', 'TRRF', 'Treasurer', 'Philip', 'G.', 'Kuehn', 'to', 'get', 'answers', 'which', 'the', 'public', 'refrigerated', 'warehousing', 'industry', 'is', 'looking', 'for.', 'Plus', 'questions', 'from', 'the', 'floor.', 'Dr.', 'Emil', 'M.', 'Mrak,', 'University', 'of', 'Cal-', 'ifornia,', 'Chairman,', 'TRRF', 'Board;', 'Sam', 'R.', 'Cecil,', 'University', 'of', 'Georgia', 'College', 'of', 'Agriculture;', 'Dr.', 'Stanley', 'Charm,', 'Tufts', 'University', 'School', 'of', 'Medicine;', 'Dr.', 'Robert', 'H.', 'Cotton,', 'ITT', 'Continental', 'Baking', 'Company;', 'Dr.', 'Owen', 'Fennema,', 'University', 'of', 'Wis-', 'consin;', 'Dr.', 'Robert', 'E.', 'Hardenburg,', 'USDA.', 'Questions', 'and', 'Answers', 'Exhibits', 'Open', 'Capt.', 'Jack', 'Stoney', 'Room', 'TRRF', 'Scientific', 'Advisory', 'Council', 'Meeting', 'Ballroom', 'Foyer']]  # noqa: E231
													SCREAMING_SNAKE_CASE__     :Dict						    = [[[1_41, 57, 2_14, 69], [2_28, 58, 2_52, 69], [1_41, 75, 2_16, 88], [2_30, 79, 2_80, 88], [1_42, 2_60, 2_18, 2_73], [2_30, 2_61, 2_55, 2_73], [1_43, 2_79, 2_18, 2_90], [2_31, 2_82, 2_90, 2_91], [1_43, 3_42, 2_18, 3_54], [2_31, 3_45, 2_89, 3_55], [2_02, 3_62, 2_27, 3_73], [1_43, 3_79, 2_20, 3_92], [2_31, 3_82, 2_91, 3_94], [1_44, 7_14, 2_20, 7_26], [2_31, 7_15, 2_56, 7_26], [1_44, 7_32, 2_20, 7_45], [2_32, 7_36, 2_91, 7_47], [1_44, 7_69, 2_18, 7_82], [2_31, 7_70, 2_56, 7_82], [1_41, 7_88, 2_02, 8_01], [2_15, 7_91, 2_74, 8_04], [1_43, 8_26, 2_04, 8_38], [2_15, 8_26, 2_40, 8_38], [1_42, 8_44, 2_02, 8_57], [2_15, 8_47, 2_74, 8_59], [3_34, 57, 4_27, 69], [4_40, 57, 5_22, 69], [3_69, 75, 4_61, 88], [4_69, 75, 5_16, 88], [5_28, 76, 5_62, 88], [5_70, 76, 6_67, 88], [6_75, 75, 7_11, 87], [7_21, 79, 7_78, 88], [7_89, 75, 8_40, 88], [3_69, 97, 4_70, 1_07], [4_84, 94, 5_07, 1_06], [5_18, 94, 5_62, 1_07], [5_76, 94, 6_55, 1_10], [6_68, 94, 7_92, 1_09], [8_04, 95, 8_29, 1_07], [3_69, 1_13, 4_65, 1_25], [4_77, 1_16, 5_47, 1_25], [5_62, 1_13, 6_58, 1_25], [6_71, 1_16, 7_48, 1_25], [7_61, 1_13, 8_11, 1_25], [3_69, 1_31, 4_65, 1_43], [4_77, 1_33, 5_48, 1_43], [5_63, 1_30, 6_98, 1_45], [7_10, 1_30, 8_02, 1_46], [3_36, 1_71, 4_12, 1_83], [4_23, 1_71, 5_72, 1_83], [5_82, 1_70, 7_16, 1_84], [7_28, 1_71, 8_17, 1_87], [8_29, 1_71, 8_44, 1_86], [3_38, 1_97, 4_82, 2_12], [5_07, 1_96, 5_57, 2_09], [5_69, 1_96, 5_95, 2_08], [6_10, 1_96, 7_02, 2_09], [5_05, 2_14, 5_83, 2_26], [5_95, 2_14, 6_56, 2_27], [6_70, 2_15, 8_07, 2_27], [3_35, 2_59, 5_43, 2_74], [5_56, 2_59, 7_08, 2_72], [3_72, 2_79, 4_22, 2_91], [4_35, 2_79, 4_60, 2_91], [4_74, 2_79, 5_74, 2_92], [5_87, 2_78, 6_64, 2_91], [6_76, 2_78, 7_38, 2_91], [7_51, 2_79, 8_34, 2_91], [3_72, 2_98, 4_34, 3_10], [3_35, 3_41, 4_83, 3_54], [4_97, 3_41, 6_55, 3_54], [6_67, 3_41, 7_28, 3_54], [7_40, 3_41, 8_25, 3_54], [3_35, 3_60, 4_30, 3_72], [4_42, 3_60, 5_34, 3_72], [5_45, 3_59, 6_87, 3_72], [6_97, 3_60, 7_54, 3_72], [7_65, 3_60, 8_23, 3_73], [3_34, 3_78, 4_28, 3_91], [4_40, 3_78, 5_77, 3_94], [5_90, 3_78, 7_05, 3_91], [7_20, 3_78, 8_01, 3_91], [3_34, 3_97, 4_00, 4_09], [3_70, 4_16, 5_29, 4_29], [5_44, 4_16, 5_76, 4_32], [5_87, 4_16, 6_65, 4_28], [6_77, 4_16, 8_14, 4_29], [3_72, 4_35, 4_52, 4_50], [4_65, 4_34, 4_95, 4_47], [5_11, 4_34, 6_00, 4_47], [6_11, 4_36, 6_37, 4_47], [6_49, 4_36, 6_94, 4_51], [7_05, 4_38, 8_24, 4_47], [3_69, 4_53, 4_52, 4_66], [4_64, 4_54, 5_09, 4_66], [5_22, 4_53, 6_11, 4_69], [6_25, 4_53, 7_92, 4_69], [3_70, 4_72, 5_56, 4_88], [5_70, 4_72, 6_84, 4_87], [6_97, 4_72, 7_18, 4_85], [7_32, 4_72, 8_35, 4_88], [3_69, 4_90, 4_11, 5_03], [4_25, 4_90, 4_84, 5_03], [4_96, 4_90, 6_35, 5_06], [6_45, 4_90, 7_07, 5_03], [7_18, 4_91, 7_61, 5_03], [7_71, 4_90, 8_40, 5_03], [3_36, 5_10, 3_74, 5_21], [3_88, 5_10, 4_47, 5_22], [4_60, 5_10, 4_89, 5_21], [5_03, 5_10, 5_80, 5_22], [5_92, 5_09, 7_36, 5_25], [7_45, 5_09, 7_70, 5_22], [7_81, 5_09, 8_40, 5_22], [3_38, 5_28, 4_34, 5_41], [4_48, 5_28, 5_96, 5_41], [6_09, 5_27, 6_87, 5_40], [7_00, 5_28, 7_92, 5_41], [3_36, 5_46, 3_97, 5_59], [4_07, 5_46, 4_31, 5_59], [4_43, 5_46, 5_25, 5_60], [5_37, 5_46, 6_80, 5_62], [6_88, 5_46, 7_14, 5_59], [7_22, 5_46, 8_37, 5_62], [3_36, 5_65, 4_49, 5_81], [4_61, 5_65, 4_85, 5_77], [4_97, 5_65, 6_65, 5_81], [6_81, 5_65, 7_18, 5_77], [7_32, 5_65, 8_37, 5_80], [3_37, 5_84, 4_38, 5_97], [4_52, 5_83, 5_21, 5_96], [5_35, 5_84, 6_77, 5_99], [6_90, 5_83, 7_87, 5_96], [8_01, 5_83, 8_25, 5_96], [3_38, 6_02, 4_78, 6_15], [4_92, 6_02, 5_30, 6_14], [5_43, 6_02, 6_38, 6_15], [6_50, 6_02, 6_76, 6_14], [6_88, 6_02, 7_88, 6_15], [8_02, 6_02, 8_43, 6_14], [3_37, 6_21, 5_02, 6_33], [5_16, 6_21, 6_15, 6_37], [6_29, 6_21, 7_74, 6_36], [7_89, 6_21, 8_27, 6_33], [3_37, 6_39, 4_18, 6_52], [4_32, 6_40, 5_71, 6_53], [5_87, 6_39, 7_31, 6_55], [7_43, 6_39, 7_69, 6_52], [7_80, 6_39, 8_41, 6_52], [3_38, 6_58, 4_40, 6_73], [4_55, 6_58, 4_91, 6_70], [5_08, 6_58, 6_02, 6_71], [6_16, 6_58, 6_38, 6_70], [6_54, 6_58, 8_35, 6_74], [3_37, 6_77, 4_29, 6_89], [3_37, 7_14, 4_82, 7_26], [4_95, 7_14, 5_48, 7_26], [5_61, 7_14, 6_83, 7_26], [3_38, 7_70, 4_61, 7_82], [4_74, 7_69, 5_54, 7_85], [4_89, 7_88, 5_62, 8_03], [5_76, 7_88, 6_43, 8_01], [6_56, 7_87, 7_51, 8_04], [7_64, 7_88, 8_44, 8_01], [3_34, 8_25, 4_21, 8_38], [4_30, 8_24, 5_74, 8_38], [5_84, 8_24, 7_23, 8_41], [3_35, 8_44, 4_50, 8_57], [4_64, 8_43, 5_83, 8_60], [6_28, 8_62, 7_55, 8_75], [7_69, 8_61, 8_48, 8_78]]]  # noqa: E231
													# fmt: on

													self.assertListEqual(encoding.words							,							UpperCamelCase_      )
													self.assertListEqual(encoding.boxes							,							UpperCamelCase_      )

													# with apply_OCR = False
													SCREAMING_SNAKE_CASE__     :List[Any]						    = LayoutLMvaImageProcessor(apply_ocr=UpperCamelCase_      )

													SCREAMING_SNAKE_CASE__     :Dict						    = image_processing(UpperCamelCase_							,							return_tensors='pt'      )

													self.assertEqual(encoding.pixel_values.shape							,							(1, 3, 2_24, 2_24)      )







'''simple docstring'''







from __future__ import annotations

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


def    lowerCamelCase       (			UpperCAmelCase__				:  list[list[int]]				,						UpperCAmelCase__				:  list[int]				,						UpperCAmelCase__				:  list[int]				,						UpperCAmelCase__				:  int				,						UpperCAmelCase__				:  list[list[int]]				,						)			->	tuple[list[list[int]], list[list[int]]]:


							'''simple docstring'''






							SCREAMING_SNAKE_CASE__     :str						    = [
							    [0 for col in range(len(grid[0]		)		)] for row in range(len(UpperCAmelCase__		)		)
							]  # the reference grid
							SCREAMING_SNAKE_CASE__     :Any						    = 1
							SCREAMING_SNAKE_CASE__     :Dict						    = [
							    [0 for col in range(len(grid[0]		)		)] for row in range(len(UpperCAmelCase__		)		)
							]  # the action grid

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

							SCREAMING_SNAKE_CASE__     :Any						    = False  # flag that is set when search is complete
							SCREAMING_SNAKE_CASE__     :str						    = False  # flag set if we can't find expand

							while not found and not resign:
														if len(UpperCAmelCase__		) == 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()
																					SCREAMING_SNAKE_CASE__     :List[Any]						    = cell.pop()
																					SCREAMING_SNAKE_CASE__     :Optional[int]						    = next_cell[2]
																					SCREAMING_SNAKE_CASE__     :Any						    = next_cell[3]
																					SCREAMING_SNAKE_CASE__     :Dict						    = next_cell[1]

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

							SCREAMING_SNAKE_CASE__     :int						    = []
							for i in range(len(UpperCAmelCase__		)		):
														path.append(invpath[len(UpperCAmelCase__		) - 1 - i]		)
							return path, action


if __name__ == "__main__":
		UpperCamelCase_      	=	[
		    [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],
		]

		UpperCamelCase_      	=	[0, 0]
		# all coordinates are given in format [y,x]
		UpperCamelCase_      	=	[len(grid) - 1, len(grid[0]) - 1]
		UpperCamelCase_      	=	1

		# the cost map which pushes the path closer to the goal
		UpperCamelCase_      	=	[[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])):
						UpperCamelCase_      	=	abs(i - goal[0]) + abs(j - goal[1])
						if grid[i][j] == 1:
								# added extra penalty in the heuristic map
								UpperCamelCase_      	=	99

		UpperCamelCase_	,			UpperCamelCase_      	=	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])






