{"problem":{"name":"B. Beza-10","description":{"content":"Many thousand years ago, stories of a man, known as Ben-10's lost brother, got spread throughout the world. Legend says that he, whose name is Beza-10, was a very peculiar guy, with jaw-dropping abili","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10202B"},"statements":[{"statement_type":"Markdown","content":"Many thousand years ago, stories of a man, known as Ben-10's lost brother, got spread throughout the world. Legend says that he, whose name is Beza-10, was a very peculiar guy, with jaw-dropping abilities and powers. Due to that, Ben-10 got afraid that his brother would become more famous and powerful than him, so he decided to banish Beza from the dimension we live in.\n\nYears passed, and now Beza is planning his return, so he can finally get the revenge he wanted ever since he was banned. However, travelling on different dimensions is not as simple as he thought it would be, therefore, he needs your help.\n\nBeza-10 is trapped on a dimension represented as a $N$x$M$ grid. Because the spell cast on him was so powerful, the grid got filled with many traps, denoted by the character *#*, on which he can't step on, because if he did, he would suffer tremendous pain and probably die. Therefore, he can only walk on empty spaces.\n\nJust like Ben-10, Beza possesses a magical watch, which is capable of shapeshifting him into powerful forms. However, as he is on an unknown dimension, his watch no longer works as expected: he can only shapeshift into chess pieces, except the pawn. After shapeshifting into a chosen chess piece, he will move according to the rules of this specific piece, which are just like in normal chess: \n\nAlso, Beza is scared that the excessive use of his watch will break it, and, therefore, decided that he will use it at most $K$ times.\n\nInitially, assume that Beza has the form of the king chess piece, is located on the position of the grid that contains the character *'B'*, and wishes to reach the escape portal, marked with a *'P'* on the grid. He asks you what is the minimum number of movements he will require in order to escape, doing at most $K$ shapeshifts, or report that it is impossible.\n\nThe first line of input has three integers: $N$ and $M$ ($2 <= N, M <= 100$), the grid dimensions, and $K$ ($0 <= K <= 100$), which is the maximum amount of shapeshifts Beza is willing to do. The next $N$ lines contain $M$ characters each, which can be: a *'B'*, denoting the starting position of Beza-10, a *'P'*, the position of the escape portal, a *'#'*, which is a trap, or a single dot $.$, which is a free space that Beza can step on.\n\nThe output consists of a single integer, which is the minimum number of movements needed to reach the portal, doing at most $K$ shapeshifts. If it is not possible to reach the portal with the given grid and conditions, print $\\\"$-1$\\\"$ (without quotes).\n\n## Input\n\nThe first line of input has three integers: $N$ and $M$ ($2 <= N, M <= 100$), the grid dimensions, and $K$ ($0 <= K <= 100$), which is the maximum amount of shapeshifts Beza is willing to do. The next $N$ lines contain $M$ characters each, which can be: a *'B'*, denoting the starting position of Beza-10, a *'P'*, the position of the escape portal, a *'#'*, which is a trap, or a single dot $.$, which is a free space that Beza can step on.\n\n## Output\n\nThe output consists of a single integer, which is the minimum number of movements needed to reach the portal, doing at most $K$ shapeshifts. If it is not possible to reach the portal with the given grid and conditions, print $\\\"$-1$\\\"$ (without quotes).\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ H_A, H_B \\in \\mathbb{Z}^+ $ be the health points of Aodzilla and Bodzilla.  \nLet $ A_A, A_B \\in \\mathbb{Z}^+ $ be their attack values.  \nLet $ n \\in \\mathbb{Z}^+ $ be the total number of turns until both monsters die.  \nLet $ s \\in \\{A, B\\}^n $ be a strategy string, where $ s_i \\in \\{A, B\\} $ denotes the target of the $ i $-th attack.  \n\nLet $ a $ be the number of attacks on Aodzilla, $ b $ the number on Bodzilla, so $ a + b = n $.  \nLet $ S_A \\subseteq \\{1, 2, \\dots, n\\} $ be the set of attack indices targeting Aodzilla, and $ S_B $ for Bodzilla.  \n\n**Constraints**  \n1. $ \\sum_{i \\in S_A} i \\ge H_A $  \n2. $ \\sum_{i \\in S_B} i \\ge H_B $  \n3. $ S_A \\cap S_B = \\emptyset $, $ S_A \\cup S_B = \\{1, 2, \\dots, n\\} $  \n\n**Objective**  \nMinimize total damage suffered:  \n$$ D = \\sum_{t=1}^{n} \\left( A_A \\cdot \\mathbf{1}_{A \\text{ alive at } t} + A_B \\cdot \\mathbf{1}_{B \\text{ alive at } t} \\right) $$  \nsubject to the above constraints, and among all minimizing strategies, choose the lexicographically smallest $ s $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10202B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}