





'''simple docstring'''

import inspect
import unittest

from datasets import load_dataset
from packaging import version

from transformers import BeitConfig
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, require_torch_multi_gpu, 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, _config_zero_init, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
   import torch
   from torch import nn

   from transformers import (
       MODEL_MAPPING,
       BeitForImageClassification,
       BeitForMaskedImageModeling,
       BeitForSemanticSegmentation,
       BeitModel,
   )
   from transformers.models.beit.modeling_beit import BEIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
   import PIL
   from PIL import Image

   from transformers import BeitImageProcessor
class     __lowerCAmelCase					:






       """simple docstring"""





       def __init__(							self       :		Tuple	,			lowerCAmelCase__       :		str	,			lowerCAmelCase__       :		Tuple=100	,			lowerCAmelCase__       :		List[Any]=13	,			lowerCAmelCase__       :		Optional[int]=30	,			lowerCAmelCase__       :		Tuple=2	,			lowerCAmelCase__       :		Any=3	,			lowerCAmelCase__       :		str=True	,			lowerCAmelCase__       :		Dict=True	,			lowerCAmelCase__       :		List[Any]=32	,			lowerCAmelCase__       :		int=4	,			lowerCAmelCase__       :		Tuple=4	,			lowerCAmelCase__       :		Dict=37	,			lowerCAmelCase__       :		Optional[Any]="gelu"	,			lowerCAmelCase__       :		Any=0.1	,			lowerCAmelCase__       :		List[Any]=0.1	,			lowerCAmelCase__       :		List[Any]=10	,			lowerCAmelCase__       :		Dict=0.02	,			lowerCAmelCase__       :		List[Any]=3	,			lowerCAmelCase__       :		int=None	,			lowerCAmelCase__       :		Tuple=[0, 1, 2, 3]	,			)   ->					List[Any]:

            '''simple docstring'''




            _UpperCamelCase       =	parent
            _UpperCamelCase       =	100
            _UpperCamelCase       =	batch_size
            _UpperCamelCase       =	image_size
            _UpperCamelCase       =	patch_size
            _UpperCamelCase       =	num_channels
            _UpperCamelCase       =	is_training
            _UpperCamelCase       =	use_labels
            _UpperCamelCase       =	hidden_size
            _UpperCamelCase       =	num_hidden_layers
            _UpperCamelCase       =	num_attention_heads
            _UpperCamelCase       =	intermediate_size
            _UpperCamelCase       =	hidden_act
            _UpperCamelCase       =	hidden_dropout_prob
            _UpperCamelCase       =	attention_probs_dropout_prob
            _UpperCamelCase       =	type_sequence_label_size
            _UpperCamelCase       =	initializer_range
            _UpperCamelCase       =	scope
            _UpperCamelCase       =	out_indices
            _UpperCamelCase       =	num_labels

            # in BeiT, the seq length equals the number of patches + 1 (we add 1 for the [CLS] token)
            _UpperCamelCase       =	(image_size // patch_size) ** 2
            _UpperCamelCase       =	num_patches + 1





       def snake_case__						(							self       :		Dict					)   ->					Tuple:

            '''simple docstring'''




            _UpperCamelCase       =	floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]					)

            _UpperCamelCase       =	None
            _UpperCamelCase       =	None
            if self.use_labels:
                 _UpperCamelCase       =	ids_tensor([self.batch_size]	,			self.type_sequence_label_size					)
                 _UpperCamelCase       =	ids_tensor([self.batch_size, self.image_size, self.image_size]	,			self.num_labels					)

            _UpperCamelCase       =	self.get_config()

            return config, pixel_values, labels, pixel_labels





       def snake_case__						(							self       :		int					)   ->					str:

            '''simple docstring'''




            return BeitConfig(
                vocab_size=self.vocab_size	,			image_size=self.image_size	,			patch_size=self.patch_size	,			num_channels=self.num_channels	,			hidden_size=self.hidden_size	,			num_hidden_layers=self.num_hidden_layers	,			num_attention_heads=self.num_attention_heads	,			intermediate_size=self.intermediate_size	,			hidden_act=self.hidden_act	,			hidden_dropout_prob=self.hidden_dropout_prob	,			attention_probs_dropout_prob=self.attention_probs_dropout_prob	,			is_decoder=lowerCAmelCase__	,			initializer_range=self.initializer_range	,			out_indices=self.out_indices	,			)





       def snake_case__						(							self       :		str	,			lowerCAmelCase__       :		Optional[int]	,			lowerCAmelCase__       :		Optional[Any]	,			lowerCAmelCase__       :		Dict	,			lowerCAmelCase__       :		Union[str, Any]					)   ->					List[Any]:

            '''simple docstring'''




            _UpperCamelCase       =	BeitModel(config=lowerCAmelCase__					)
            model.to(lowerCAmelCase__					)
            model.eval()
            _UpperCamelCase       =	model(lowerCAmelCase__					)
            self.parent.assertEqual(result.last_hidden_state.shape	,			(self.batch_size, self.seq_length, self.hidden_size)					)





       def snake_case__						(							self       :		Dict	,			lowerCAmelCase__       :		int	,			lowerCAmelCase__       :		Tuple	,			lowerCAmelCase__       :		str	,			lowerCAmelCase__       :		Optional[int]					)   ->					List[str]:

            '''simple docstring'''




            _UpperCamelCase       =	BeitForMaskedImageModeling(config=lowerCAmelCase__					)
            model.to(lowerCAmelCase__					)
            model.eval()
            _UpperCamelCase       =	model(lowerCAmelCase__					)
            self.parent.assertEqual(result.logits.shape	,			(self.batch_size, self.seq_length - 1, self.vocab_size)					)





       def snake_case__						(							self       :		Dict	,			lowerCAmelCase__       :		List[Any]	,			lowerCAmelCase__       :		int	,			lowerCAmelCase__       :		Union[str, Any]	,			lowerCAmelCase__       :		Dict					)   ->					List[Any]:

            '''simple docstring'''




            _UpperCamelCase       =	self.type_sequence_label_size
            _UpperCamelCase       =	BeitForImageClassification(lowerCAmelCase__					)
            model.to(lowerCAmelCase__					)
            model.eval()
            _UpperCamelCase       =	model(lowerCAmelCase__	,			labels=lowerCAmelCase__					)
            self.parent.assertEqual(result.logits.shape	,			(self.batch_size, self.type_sequence_label_size)					)

            # test greyscale images
            _UpperCamelCase       =	1
            _UpperCamelCase       =	BeitForImageClassification(lowerCAmelCase__					)
            model.to(lowerCAmelCase__					)
            model.eval()

            _UpperCamelCase       =	floats_tensor([self.batch_size, 1, self.image_size, self.image_size]					)
            _UpperCamelCase       =	model(lowerCAmelCase__	,			labels=lowerCAmelCase__					)
            self.parent.assertEqual(result.logits.shape	,			(self.batch_size, self.type_sequence_label_size)					)





       def snake_case__						(							self       :		str	,			lowerCAmelCase__       :		Any	,			lowerCAmelCase__       :		Optional[Any]	,			lowerCAmelCase__       :		List[str]	,			lowerCAmelCase__       :		Any					)   ->					Tuple:

            '''simple docstring'''




            _UpperCamelCase       =	self.num_labels
            _UpperCamelCase       =	BeitForSemanticSegmentation(lowerCAmelCase__					)
            model.to(lowerCAmelCase__					)
            model.eval()
            _UpperCamelCase       =	model(lowerCAmelCase__					)
            self.parent.assertEqual(
                result.logits.shape	,			(self.batch_size, self.num_labels, self.image_size * 2, self.image_size * 2)					)
            _UpperCamelCase       =	model(lowerCAmelCase__	,			labels=lowerCAmelCase__					)
            self.parent.assertEqual(
                result.logits.shape	,			(self.batch_size, self.num_labels, self.image_size * 2, self.image_size * 2)					)







       def snake_case__						(							self       :		Optional[int]					)   ->					Union[str, Any]:

            '''simple docstring'''




            _UpperCamelCase       =	self.prepare_config_and_inputs()
            _UpperCamelCase   ,    _UpperCamelCase   ,    _UpperCamelCase   ,    _UpperCamelCase       =	config_and_inputs
            _UpperCamelCase       =	{'''pixel_values''': pixel_values}
            return config, inputs_dict

@require_torch
class     __lowerCAmelCase					(   __magic_name__						,						__magic_name__						,						unittest.TestCase			):






       """simple docstring"""
       _snake_case     :					Optional[int]						    =   (
           (BeitModel, BeitForImageClassification, BeitForMaskedImageModeling, BeitForSemanticSegmentation)
           if is_torch_available()
           else ()
       )
       _snake_case     :					Tuple						    =   (
           {
               'feature-extraction': BeitModel,
               'image-classification': BeitForImageClassification,
               'image-segmentation': BeitForSemanticSegmentation,
           }
           if is_torch_available()
           else {}
       )

       _snake_case     :					Any						    =   False
       _snake_case     :					Dict						    =   False
       _snake_case     :					Tuple						    =   False





       def snake_case__						(							self       :		Dict					)   ->					Dict:

            '''simple docstring'''




            _UpperCamelCase       =	BeitModelTester(self					)
            _UpperCamelCase       =	ConfigTester(self	,			config_class=lowerCAmelCase__	,			has_text_modality=lowerCAmelCase__	,			hidden_size=37					)





       def snake_case__						(							self       :		str					)   ->					int:

            '''simple docstring'''




            self.config_tester.run_common_tests()





       @unittest.skip(reason='''BEiT does not use inputs_embeds'''					)
       def snake_case__						(							self       :		Dict					)   ->					List[Any]:

            '''simple docstring'''




            pass





       @require_torch_multi_gpu
       @unittest.skip(reason='''BEiT has some layers using `add_module` which doesn\'t work well with `nn.DataParallel`'''					)
       def snake_case__						(							self       :		Any					)   ->					Any:

            '''simple docstring'''




            pass





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

            '''simple docstring'''




            _UpperCamelCase   ,    _UpperCamelCase       =	self.model_tester.prepare_config_and_inputs_for_common()

            for model_class in self.all_model_classes:
                 _UpperCamelCase       =	model_class(lowerCAmelCase__					)
                 self.assertIsInstance(model.get_input_embeddings()	,			(nn.Module)					)
                 _UpperCamelCase       =	model.get_output_embeddings()
                 self.assertTrue(x is None or isinstance(lowerCAmelCase__	,			nn.Linear					)					)





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

            '''simple docstring'''




            _UpperCamelCase   ,    _UpperCamelCase       =	self.model_tester.prepare_config_and_inputs_for_common()

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

                 _UpperCamelCase       =	['''pixel_values''']
                 self.assertListEqual(arg_names[:1]	,			lowerCAmelCase__					)





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

            '''simple docstring'''




            _UpperCamelCase       =	self.model_tester.prepare_config_and_inputs()
            self.model_tester.create_and_check_model(*lowerCAmelCase__					)





       def snake_case__						(							self       :		Dict					)   ->					str:

            '''simple docstring'''




            _UpperCamelCase       =	self.model_tester.prepare_config_and_inputs()
            self.model_tester.create_and_check_for_masked_lm(*lowerCAmelCase__					)





       def snake_case__						(							self       :		Dict					)   ->					Tuple:

            '''simple docstring'''




            _UpperCamelCase       =	self.model_tester.prepare_config_and_inputs()
            self.model_tester.create_and_check_for_image_classification(*lowerCAmelCase__					)





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

            '''simple docstring'''




            _UpperCamelCase       =	self.model_tester.prepare_config_and_inputs()
            self.model_tester.create_and_check_for_semantic_segmentation(*lowerCAmelCase__					)





       def snake_case__						(							self       :		Optional[int]					)   ->					Optional[Any]:

            '''simple docstring'''




            if not self.model_tester.is_training:
                 return

            _UpperCamelCase   ,    _UpperCamelCase       =	self.model_tester.prepare_config_and_inputs_for_common()
            _UpperCamelCase       =	True

            for model_class in self.all_model_classes:
                 # we don't test BeitForMaskedImageModeling
                 if model_class in [*get_values(lowerCAmelCase__					), BeitForMaskedImageModeling]:
                      continue

                 _UpperCamelCase       =	model_class(lowerCAmelCase__					)
                 model.to(lowerCAmelCase__					)
                 model.train()
                 _UpperCamelCase       =	self._prepare_for_class(lowerCAmelCase__	,			lowerCAmelCase__	,			return_labels=lowerCAmelCase__					)
                 _UpperCamelCase       =	model(**lowerCAmelCase__					).loss
                 loss.backward()





       def snake_case__						(							self       :		int					)   ->					str:

            '''simple docstring'''




            _UpperCamelCase   ,    _UpperCamelCase       =	self.model_tester.prepare_config_and_inputs_for_common()
            if not self.model_tester.is_training:
                 return

            _UpperCamelCase       =	False
            _UpperCamelCase       =	True

            for model_class in self.all_model_classes:
                 # we don't test BeitForMaskedImageModeling
                 if (
                     model_class in [*get_values(lowerCAmelCase__					), BeitForMaskedImageModeling]
                     or not model_class.supports_gradient_checkpointing
                 ):
                      continue

                 _UpperCamelCase       =	model_class(lowerCAmelCase__					)
                 model.gradient_checkpointing_enable()
                 model.to(lowerCAmelCase__					)
                 model.train()
                 _UpperCamelCase       =	self._prepare_for_class(lowerCAmelCase__	,			lowerCAmelCase__	,			return_labels=lowerCAmelCase__					)
                 _UpperCamelCase       =	model(**lowerCAmelCase__					).loss
                 loss.backward()





       def snake_case__						(							self       :		Dict					)   ->					Any:

            '''simple docstring'''




            _UpperCamelCase   ,    _UpperCamelCase       =	self.model_tester.prepare_config_and_inputs_for_common()

            _UpperCamelCase       =	_config_zero_init(lowerCAmelCase__					)
            for model_class in self.all_model_classes:
                 _UpperCamelCase       =	model_class(config=lowerCAmelCase__					)
                 for name, param in model.named_parameters():
                      # we skip lambda parameters as these require special initial values
                      # determined by config.layer_scale_init_value
                      if "lambda" in name:
                           continue
                      if param.requires_grad:
                           self.assertIn(
                               ((param.data.mean() * 1e9).round() / 1e9).item()	,			[0.0, 1.0]	,			msg=f"""Parameter {name} of model {model_class} seems not properly initialized"""	,			)







       @slow
       def snake_case__						(							self       :		str					)   ->					Optional[int]:

            '''simple docstring'''




            for model_name in BEIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
                 _UpperCamelCase       =	BeitModel.from_pretrained(lowerCAmelCase__					)
                 self.assertIsNotNone(lowerCAmelCase__					)







def  a__    (    )		->		Dict:





     """simple docstring"""

     _UpperCamelCase       =	Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png'''				)
     return image




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






       """simple docstring"""





       @cached_property
       def snake_case__						(							self       :		str					)   ->					Any:

            '''simple docstring'''




            return BeitImageProcessor.from_pretrained('''microsoft/beit-base-patch16-224'''					) if is_vision_available() else None





       @slow
       def snake_case__						(							self       :		Any					)   ->					List[Any]:

            '''simple docstring'''




            _UpperCamelCase       =	BeitForMaskedImageModeling.from_pretrained('''microsoft/beit-base-patch16-224-pt22k'''					).to(lowerCAmelCase__					)

            _UpperCamelCase       =	self.default_image_processor
            _UpperCamelCase       =	prepare_img()
            _UpperCamelCase       =	image_processor(images=lowerCAmelCase__	,			return_tensors='''pt'''					).pixel_values.to(lowerCAmelCase__					)

            # prepare bool_masked_pos
            _UpperCamelCase       =	torch.ones((1, 196)	,			dtype=torch.bool					).to(lowerCAmelCase__					)

            # forward pass
            with torch.no_grad():
                 _UpperCamelCase       =	model(pixel_values=lowerCAmelCase__	,			bool_masked_pos=lowerCAmelCase__					)
            _UpperCamelCase       =	outputs.logits

            # verify the logits
            _UpperCamelCase       =	torch.Size((1, 196, 8192)					)
            self.assertEqual(logits.shape	,			lowerCAmelCase__					)

            _UpperCamelCase       =	torch.tensor(
                [[-3.2437, 0.5072, -13.9174], [-3.2456, 0.4948, -13.9401], [-3.2033, 0.5121, -13.8550]]					).to(lowerCAmelCase__					)

            self.assertTrue(torch.allclose(logits[bool_masked_pos][:3, :3]	,			lowerCAmelCase__	,			atol=1e-2					)					)





       @slow
       def snake_case__						(							self       :		Dict					)   ->					Union[str, Any]:

            '''simple docstring'''




            _UpperCamelCase       =	BeitForImageClassification.from_pretrained('''microsoft/beit-base-patch16-224'''					).to(lowerCAmelCase__					)

            _UpperCamelCase       =	self.default_image_processor
            _UpperCamelCase       =	prepare_img()
            _UpperCamelCase       =	image_processor(images=lowerCAmelCase__	,			return_tensors='''pt'''					).to(lowerCAmelCase__					)

            # forward pass
            with torch.no_grad():
                 _UpperCamelCase       =	model(**lowerCAmelCase__					)
            _UpperCamelCase       =	outputs.logits

            # verify the logits
            _UpperCamelCase       =	torch.Size((1, 1000)					)
            self.assertEqual(logits.shape	,			lowerCAmelCase__					)

            _UpperCamelCase       =	torch.tensor([-1.2385, -1.0987, -1.0108]					).to(lowerCAmelCase__					)

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

            _UpperCamelCase       =	281
            self.assertEqual(logits.argmax(-1					).item()	,			lowerCAmelCase__					)





       @slow
       def snake_case__						(							self       :		List[str]					)   ->					Any:

            '''simple docstring'''




            _UpperCamelCase       =	BeitForImageClassification.from_pretrained('''microsoft/beit-large-patch16-224-pt22k-ft22k'''					).to(
                lowerCAmelCase__					)

            _UpperCamelCase       =	self.default_image_processor
            _UpperCamelCase       =	prepare_img()
            _UpperCamelCase       =	image_processor(images=lowerCAmelCase__	,			return_tensors='''pt'''					).to(lowerCAmelCase__					)

            # forward pass
            with torch.no_grad():
                 _UpperCamelCase       =	model(**lowerCAmelCase__					)
            _UpperCamelCase       =	outputs.logits

            # verify the logits
            _UpperCamelCase       =	torch.Size((1, 21841)					)
            self.assertEqual(logits.shape	,			lowerCAmelCase__					)

            _UpperCamelCase       =	torch.tensor([1.6881, -0.2787, 0.5901]					).to(lowerCAmelCase__					)

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

            _UpperCamelCase       =	2396
            self.assertEqual(logits.argmax(-1					).item()	,			lowerCAmelCase__					)





       @slow
       def snake_case__						(							self       :		Union[str, Any]					)   ->					int:

            '''simple docstring'''




            _UpperCamelCase       =	BeitForSemanticSegmentation.from_pretrained('''microsoft/beit-base-finetuned-ade-640-640'''					)
            _UpperCamelCase       =	model.to(lowerCAmelCase__					)

            _UpperCamelCase       =	BeitImageProcessor(do_resize=lowerCAmelCase__	,			size=640	,			do_center_crop=lowerCAmelCase__					)

            _UpperCamelCase       =	load_dataset('''hf-internal-testing/fixtures_ade20k'''	,			split='''test'''					)
            _UpperCamelCase       =	Image.open(ds[0]['''file''']					)
            _UpperCamelCase       =	image_processor(images=lowerCAmelCase__	,			return_tensors='''pt'''					).to(lowerCAmelCase__					)

            # forward pass
            with torch.no_grad():
                 _UpperCamelCase       =	model(**lowerCAmelCase__					)
            _UpperCamelCase       =	outputs.logits

            # verify the logits
            _UpperCamelCase       =	torch.Size((1, 150, 160, 160)					)
            self.assertEqual(logits.shape	,			lowerCAmelCase__					)

            _UpperCamelCase       =	version.parse(PIL.__version__					) < version.parse('''9.0.0'''					)

            if is_pillow_less_than_a:
                 _UpperCamelCase       =	torch.tensor(
                     [
                         [[-4.9225, -2.3954, -3.0522], [-2.8822, -1.0046, -1.7561], [-2.9549, -1.3228, -2.1347]],
                         [[-5.8168, -3.4129, -4.0778], [-3.8651, -2.2214, -3.0277], [-3.8356, -2.4643, -3.3535]],
                         [[-0.0078, 3.9952, 4.0754], [2.9856, 4.6944, 5.0035], [3.2413, 4.7813, 4.9969]],
                     ]	,			device=lowerCAmelCase__	,			)
            else:
                 _UpperCamelCase       =	torch.tensor(
                     [
                         [[-4.8960, -2.3688, -3.0355], [-2.8478, -0.9836, -1.7418], [-2.9449, -1.3332, -2.1456]],
                         [[-5.8081, -3.4124, -4.1006], [-3.8561, -2.2081, -3.0323], [-3.8365, -2.4601, -3.3669]],
                         [[-0.0309, 3.9868, 4.0540], [2.9640, 4.6877, 4.9976], [3.2081, 4.7690, 4.9942]],
                     ]	,			device=lowerCAmelCase__	,			)

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







       @slow
       def snake_case__						(							self       :		str					)   ->					List[str]:

            '''simple docstring'''




            _UpperCamelCase       =	BeitForSemanticSegmentation.from_pretrained('''microsoft/beit-base-finetuned-ade-640-640'''					)
            _UpperCamelCase       =	model.to(lowerCAmelCase__					)

            _UpperCamelCase       =	BeitImageProcessor(do_resize=lowerCAmelCase__	,			size=640	,			do_center_crop=lowerCAmelCase__					)

            _UpperCamelCase       =	load_dataset('''hf-internal-testing/fixtures_ade20k'''	,			split='''test'''					)
            _UpperCamelCase       =	Image.open(ds[0]['''file''']					)
            _UpperCamelCase       =	image_processor(images=lowerCAmelCase__	,			return_tensors='''pt'''					).to(lowerCAmelCase__					)

            # forward pass
            with torch.no_grad():
                 _UpperCamelCase       =	model(**lowerCAmelCase__					)

            _UpperCamelCase       =	outputs.logits.detach().cpu()

            _UpperCamelCase       =	image_processor.post_process_semantic_segmentation(outputs=lowerCAmelCase__	,			target_sizes=[(500, 300)]					)
            _UpperCamelCase       =	torch.Size((500, 300)					)
            self.assertEqual(segmentation[0].shape	,			lowerCAmelCase__					)

            _UpperCamelCase       =	image_processor.post_process_semantic_segmentation(outputs=lowerCAmelCase__					)
            _UpperCamelCase       =	torch.Size((160, 160)					)
            self.assertEqual(segmentation[0].shape	,			lowerCAmelCase__					)










'''simple docstring'''

def  a__    (    lowercase :					int, lowercase :					int, lowercase :					list[list[int]]				)		->		int:





     """simple docstring"""

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

          _UpperCamelCase       =	update_area_of_max_square(lowercase, col + 1				)
          _UpperCamelCase       =	update_area_of_max_square(row + 1, col + 1				)
          _UpperCamelCase       =	update_area_of_max_square(row + 1, lowercase				)

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

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







def  a__    (    lowercase :					int, lowercase :					int, lowercase :					list[list[int]]				)		->		int:





     """simple docstring"""

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

          _UpperCamelCase       =	update_area_of_max_square_using_dp_array(lowercase, col + 1, lowercase				)
          _UpperCamelCase       =	update_area_of_max_square_using_dp_array(row + 1, col + 1, lowercase				)
          _UpperCamelCase       =	update_area_of_max_square_using_dp_array(row + 1, lowercase, lowercase				)

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

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

     return largest_square_area[0]







def  a__    (    lowercase :					int, lowercase :					int, lowercase :					list[list[int]]				)		->		int:





     """simple docstring"""

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

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

     return largest_square_area







def  a__    (    lowercase :					int, lowercase :					int, lowercase :					list[list[int]]				)		->		int:





     """simple docstring"""

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

               if mat[row][col] == 1:
                    _UpperCamelCase       =	1 + min(lowercase, lowercase, lowercase				)
                    _UpperCamelCase       =	max(current_row[col], lowercase				)
               else:
                    _UpperCamelCase       =	0
          _UpperCamelCase       =	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]]))



