




def 					lowerCamelCase__       (						A__       :					list[list[int]]  ,			A__       :					int  ,			A__       :					int  ,			A__       :					set	):





       '''simple docstring'''



       __lowerCamelCase,   __lowerCamelCase   =						len(A__	), len(grid[0]	)
       if (
           min(A__  ,			A__	) < 0
           or row == row_length
           or col == col_length
           or (row, col) in visit
           or grid[row][col] == 1
       ):
              return 0
       if row == row_length - 1 and col == col_length - 1:
              return 1

       visit.add((row, col)	)

       __lowerCamelCase   =						0
       count += depth_first_search(A__  ,			row + 1  ,			A__  ,			A__	)
       count += depth_first_search(A__  ,			row - 1  ,			A__  ,			A__	)
       count += depth_first_search(A__  ,			A__  ,			col + 1  ,			A__	)
       count += depth_first_search(A__  ,			A__  ,			col - 1  ,			A__	)

       visit.remove((row, col)	)
       return count


if __name__ == "__main__":
       import doctest

       doctest.testmod()







import unittest

from transformers import BigBirdConfig, is_flax_available
from transformers.testing_utils import require_flax, slow

from ...test_modeling_flax_common import FlaxModelTesterMixin, ids_tensor, random_attention_mask


if is_flax_available():
       import jax

       from transformers.models.big_bird.modeling_flax_big_bird import (
           FlaxBigBirdForCausalLM,
           FlaxBigBirdForMaskedLM,
           FlaxBigBirdForMultipleChoice,
           FlaxBigBirdForPreTraining,
           FlaxBigBirdForQuestionAnswering,
           FlaxBigBirdForSequenceClassification,
           FlaxBigBirdForTokenClassification,
           FlaxBigBirdModel,
       )





class     lowerCamelCase__(					unittest.TestCase):
      def __init__(				self: Optional[int]    ,       UpperCamelCase_: Any    ,       UpperCamelCase_: int=2    ,       UpperCamelCase_: Optional[Any]=56    ,       UpperCamelCase_: Tuple=True    ,       UpperCamelCase_: Union[str, Any]=True    ,       UpperCamelCase_: Optional[Any]=True    ,       UpperCamelCase_: str=True    ,       UpperCamelCase_: str=99    ,       UpperCamelCase_: Tuple=32    ,       UpperCamelCase_: int=2    ,       UpperCamelCase_: Optional[int]=2    ,       UpperCamelCase_: Tuple=7    ,       UpperCamelCase_: Optional[int]="gelu_new"    ,       UpperCamelCase_: Any=0.1    ,       UpperCamelCase_: List[str]=0.1    ,       UpperCamelCase_: List[Any]=5_12    ,       UpperCamelCase_: Union[str, Any]=16    ,       UpperCamelCase_: int=2    ,       UpperCamelCase_: Dict=0.02    ,       UpperCamelCase_: Tuple=4    ,       UpperCamelCase_: Union[str, Any]="block_sparse"    ,       UpperCamelCase_: Optional[Any]=True    ,       UpperCamelCase_: Any=False    ,       UpperCamelCase_: Any=2    ,       UpperCamelCase_: int=3    ,       ):
             __lowerCamelCase   =						parent
             __lowerCamelCase   =						batch_size
             __lowerCamelCase   =						seq_length
             __lowerCamelCase   =						is_training
             __lowerCamelCase   =						use_attention_mask
             __lowerCamelCase   =						use_token_type_ids
             __lowerCamelCase   =						use_labels
             __lowerCamelCase   =						vocab_size
             __lowerCamelCase   =						hidden_size
             __lowerCamelCase   =						num_hidden_layers
             __lowerCamelCase   =						num_attention_heads
             __lowerCamelCase   =						intermediate_size
             __lowerCamelCase   =						hidden_act
             __lowerCamelCase   =						hidden_dropout_prob
             __lowerCamelCase   =						attention_probs_dropout_prob
             __lowerCamelCase   =						max_position_embeddings
             __lowerCamelCase   =						type_vocab_size
             __lowerCamelCase   =						type_sequence_label_size
             __lowerCamelCase   =						initializer_range
             __lowerCamelCase   =						num_choices

             __lowerCamelCase   =						rescale_embeddings
             __lowerCamelCase   =						attention_type
             __lowerCamelCase   =						use_bias
             __lowerCamelCase   =						block_size
             __lowerCamelCase   =						num_random_blocks
      def 			lowerCAmelCase__						(				self: int   ):
             __lowerCamelCase   =						ids_tensor([self.batch_size, self.seq_length]    ,       self.vocab_size   )

             __lowerCamelCase   =						None
             if self.use_attention_mask:
                    __lowerCamelCase   =						random_attention_mask([self.batch_size, self.seq_length]   )

             __lowerCamelCase   =						None
             if self.use_token_type_ids:
                    __lowerCamelCase   =						ids_tensor([self.batch_size, self.seq_length]    ,       self.type_vocab_size   )

             __lowerCamelCase   =						BigBirdConfig(
                 vocab_size=self.vocab_size    ,       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    ,       max_position_embeddings=self.max_position_embeddings    ,       type_vocab_size=self.type_vocab_size    ,       is_decoder=UpperCamelCase_    ,       initializer_range=self.initializer_range    ,       attention_type=self.attention_type    ,       block_size=self.block_size    ,       num_random_blocks=self.num_random_blocks    ,       use_bias=self.use_bias    ,       rescale_embeddings=self.rescale_embeddings    ,       )

             return config, input_ids, token_type_ids, attention_mask




      def 			lowerCAmelCase__						(				self: Dict   ):
             __lowerCamelCase   =						self.prepare_config_and_inputs()
             __lowerCamelCase,   __lowerCamelCase,   __lowerCamelCase,   __lowerCamelCase   =						config_and_inputs
             __lowerCamelCase   =						{
                 """input_ids""": input_ids,
                 """token_type_ids""": token_type_ids,
                 """attention_mask""": attention_mask,
             }
             return config, inputs_dict





@require_flax
class     lowerCamelCase__(					__lowerCamelCase ,     unittest.TestCase):
      UpperCAmelCase__      :	Optional[int]    		=   (
          (
              FlaxBigBirdForCausalLM,
              FlaxBigBirdModel,
              FlaxBigBirdForPreTraining,
              FlaxBigBirdForMaskedLM,
              FlaxBigBirdForMultipleChoice,
              FlaxBigBirdForQuestionAnswering,
              FlaxBigBirdForSequenceClassification,
              FlaxBigBirdForTokenClassification,
          )
          if is_flax_available()
          else ()
      )

      UpperCAmelCase__      :	Optional[int]    		=   False
      UpperCAmelCase__      :	Optional[int]    		=   False
      def 			lowerCAmelCase__						(				self: List[str]   ):
             __lowerCamelCase   =						FlaxBigBirdModelTester(self   )
      @slow
      # copied from `test_modeling_flax_common` because it takes much longer than other models
      def 			lowerCAmelCase__						(				self: Optional[Any]   ):
             super().test_from_pretrained_save_pretrained()
      @slow
      # copied from `test_modeling_flax_common` because it takes much longer than other models
      def 			lowerCAmelCase__						(				self: List[Any]   ):
             super().test_from_pretrained_with_no_automatic_init()
      @slow
      # copied from `test_modeling_flax_common` because it takes much longer than other models
      def 			lowerCAmelCase__						(				self: List[Any]   ):
             super().test_no_automatic_init()
      @slow
      # copied from `test_modeling_flax_common` because it takes much longer than other models
      def 			lowerCAmelCase__						(				self: List[str]   ):
             super().test_hidden_states_output()
      @slow
      def 			lowerCAmelCase__						(				self: Optional[Any]   ):
             for model_class_name in self.all_model_classes:
                    __lowerCamelCase   =						model_class_name.from_pretrained("""google/bigbird-roberta-base"""   )
                    self.assertIsNotNone(UpperCamelCase_   )
      def 			lowerCAmelCase__						(				self: Dict   ):
             if self.test_attn_probs:
                    super().test_attention_outputs()
      @slow
      # copied from `test_modeling_flax_common` because it takes much longer than other models
      def 			lowerCAmelCase__						(				self: List[Any]   ):
             __lowerCamelCase,   __lowerCamelCase   =						self.model_tester.prepare_config_and_inputs_for_common()

             for model_class in self.all_model_classes:
                    with self.subTest(model_class.__name__   ):
                           __lowerCamelCase   =						self._prepare_for_class(UpperCamelCase_    ,       UpperCamelCase_   )
                           __lowerCamelCase   =						model_class(UpperCamelCase_   )

                           @jax.jit
                           def model_jitted(UpperCamelCase_: Tuple    ,       UpperCamelCase_: List[Any]=None    ,       **UpperCamelCase_: Union[str, Any]   ):
                                  return model(input_ids=UpperCamelCase_    ,       attention_mask=UpperCamelCase_    ,       **UpperCamelCase_   )

                           with self.subTest("""JIT Enabled"""   ):
                                  __lowerCamelCase   =						model_jitted(**UpperCamelCase_   ).to_tuple()

                           with self.subTest("""JIT Disabled"""   ):
                                  with jax.disable_jit():
                                         __lowerCamelCase   =						model_jitted(**UpperCamelCase_   ).to_tuple()

                           self.assertEqual(len(UpperCamelCase_   )    ,       len(UpperCamelCase_   )   )
                           for jitted_output, output in zip(UpperCamelCase_    ,       UpperCamelCase_   ):
                                  self.assertEqual(jitted_output.shape    ,       output.shape   )




      def 			lowerCAmelCase__						(				self: List[Any]    ,       UpperCamelCase_: int    ,       UpperCamelCase_: List[str]    ,       UpperCamelCase_: Any    ,       UpperCamelCase_: Dict=1E-5    ,       UpperCamelCase_: List[str]="outputs"    ,       UpperCamelCase_: List[str]=None   ):
             # `bigbird_block_sparse_attention` in `FlaxBigBird` returns `attention_probs = None`, while in PyTorch version,
             # an effort was done to return `attention_probs` (yet to be verified).
             if name.startswith("""outputs.attentions"""   ):
                    return
             else:
                    super().check_pt_flax_outputs(UpperCamelCase_    ,       UpperCamelCase_    ,       UpperCamelCase_    ,       UpperCamelCase_    ,       UpperCamelCase_    ,       UpperCamelCase_   )

