Retaining Water

Statement

François designs above-ground swimming pools for decadent members of the CG bourgeoisie. His designs are represented by an NxN grid of letters, with heights ranging from A=1 to Z=26. Find the volume of water each pool can hold.

Input description

<<Line 1:>> The size [[N]] of the grid. <<Next [[N]] lines:>> The grid values.

Output description

The volume of water that the pool can hold. Outside the pool the height is 0, so no water is held on the cells at the edge of the pool.

Constraints

10 ≤ [[N]] ≤ 40

Game modes

Fastest

Test cases

Test 1 Test

Input

10 ZZZZZZZZZZ ZAAAAAAAAZ ZAAAAAAAAZ ZAAAAAAAAZ ZAAAAAAAAZ ZAAAAAAAAZ ZAAAAAAAAZ ZAAAAAAAAZ ZAAAAAAAAZ ZZZZZZZZZZ

Output

1600

Validator 1 Validator

Input

10 ZZZZZZZZZZ RAAAAZEEEZ RAAAAZEEEZ RAAAAZEEEZ RAAAAZEEEZ RAAAAAEEEZ RAAAAZEEEZ RAAAAZEEEZ QAAAAZEEEZ ZZZZZZZZZZ

Output

816

Test 2 Test

Input

20 DDDDDDDDDDDDDDDDDDDD DAAAAAAAAAAAABBBCCCC DAAAAAAAAAAAABBBDDDD DAAAAAAAAAAAABBBDDDD DAAAAAAAAAAAABBBEEFF GGGGGGGGGHHHIIJJEEFF GGGGGGGGGHHHIIJJEEFF KKKKKLLLLHHHIIJJMMMM KKKKKLLLLNNOOPPPMMMM QQQQRRSSSNNOOPPPTTTT QQQQRRSSSNNOOUUUTTTT VVVVRRWWWNNXXUUUYYYY VVVVRRWWWZZXXAAAYYYY VVVVBBBBBZZXXAAAYYYY VVVVBBBBBZZCCCDDEEFR GGGHHHIIIJJCCCDDEEFR GGGHHHIIIJJKKKDDEEFR GGGHHHIIIJJKKKDDEEFR LLLLLLLLLLLLLMMMMNNR FFFFFFFFFFFFFFFFFFFF

Output

368

Validator 2 Validator

Input

20 SSSSSSSSSSSSSSSSSSSS SAAAAAAAAAAAAAAAAAAS SAAAAAAAAAAAAAAAAAAS UBCCDDEEFFFGGGGHHHII UBCCDDEEFFFGGGGHHHII UBCCDDEEJJJKKKKLLLII UBCCDDEEJJJKKKKLLLII UBCCDDMMMNNNNNNLLLII UBOODDMMMPPPPPPQQQII UBOODDMMMRRRRRRQQQSS UBOOTTTUUUUUVVVQQQSS UBOOTTTUUUUUVVVQQQSS UBWWWXXXYYYYZZZAAASS UBWWWXXXYYYYZZZAAASS UBBBBCCCYYYYDDEEFFSS UBBBBCCCGGHHDDEEFFSS UBIIIIJJGGHHDDEEFFSS UBIIIIJJGGHHKKKLLLSS UBIIIIJJMMMMKKKLLLSS UUIIIIJJMMMMNNNNNNSS

Output

818

Test 3 Test

Input

30 YENZRGRNFKINMCAGFMMGJWVZZRVCWQ KKBAQPBNSWUXIDFHDZYNTOGTSAEKVS EGTLNXYWRHLLYTNGOYBLULNOIGVMFV WKNZBYVPCWLXZSESPZKIACDBLGNTJZ MUREWDLLJVTOGPOHWPGIRUDOLEGTRL LZKAVBAYBMNMOAAQGQKDCHGNOIBNNZ URHBKIZDYSCPSGEHRIGIFEUYAWLYLX YASRATWMWKORQIJYHKCYSWRLZIYBYX YCDYJTUOFHCWTEXEWIOJFUVVFSJLWL GUAWVRQETAUNHQLMARPFPFXCRRGVOI TGMCABQJLFBRCYDQMWEKZJBYBFMADN GZMUVJKJFZSEWAMIIZWPMWLOQRQJJH JOCNZHLCORENIIJQINMRKZDOKPYJNW MDGUSXCCKXWQGCFZRBDFGTCHHBFGSB QYAZGXUEUMZFUDCSGJZUFGHGUUBWIH NUVZDLUUYJYRGQSYHJJUKIAJGEKUQN CNBQBDXAFDXNMLSZUOCLOCGYKVOVNE PARZOFUPFZTGRITQXCMOZKXHCKBRMA IVOKPXQGEHOMLSWIEATJUXAEDBKUFJ XVLSZSAOWZOEQCZWBKOTWHNGFQNOQN ORYFEBJITOHJHJZHCLJNFZRGLHQRJA KZYENAUZGROOZIPCBKRBUNJWUPJRIG YNEPCOUEPQFEGGXSTLKWKJJJJORUZB GFNHOUWLRQVESEOFDMBQQDCACXLGYF EBNNJKZYYOGGVUIDIEROUTFNNSBBXB BHRKDBVBBLEMPYVOOKGUPUGAQNMBGT ZDOLHRCSCLHTIXRPCTZMFQXCRNNMUT SXBRAATOMKNRFGEMNEZKCSXMPKKMJV DKMJHUYLWSHBIXJHMXEOSTLMEXUPQB SZJSOCBQVELVOOWHGJCTSQOYNFTOKP

Output

2440

Validator 3 Validator

Input

30 UHSUTOVBICTUWRXAGJMMMZSWOMFMLU VIJVJZQRDCFEBEXUOESIMXGOGIXMMC MDKRXTCFPVNEJVAUMSZDYFYAEZPRUZ JCOOBFACVUUPKAKANZRZQSQBWDKSDR WCTUXOCTLXKZIMEKAUNZQDYQKWCNBJ GEWUPKOTYBTFTCKAGEVEYCOSGTXROL IKJXKDTHUOBXQBVKETABMFPOPFZVVN EEKLXQDEERRQUDTKLEUEYVRYMSXEOQ VKVAJXHESWTXKKOLTJPRKVJIAKLUPD JYNLLGKKWHUIJEDLURIYEFEHRHGPLC WQWOPOXESLBUANYVZHWPCEABHAJMYP IYWFKFSWDBKNHKBNJDELFZSBCNVQUS UJBNUJKTNJBDQGZYPJPJVMGPVRIVAO IUKAMFSQHXQCNTOBNFHBMVCXIGDAOI ZLLLNNOGVPLMTBMEJPHYSQZTDGXSGD SGXSNMTXEXISHHOIWREHTZQDYMCBJT WATWXZYRSGGMIPFAQXNNESGAQOIGDW CEPUNNESDUDOQGZRQOSVJZMKGYJZZI LDOTEKYKWMNQQWIMLOYPKDJKHWCLNL WBDNCGDXYXCUMAWEENXUPAJWIATRGI TXXRKLEMGIKFBFKQNPBONVYMHAGCZI CKSMYLKMEEDTGQWFTJFBYXKGKWTQZZ FJBLBDXSFEMEKDJMTKXXPRSWTOKXNU LWNIMFLYRRCANFUNRAUGGCJLHSRIIK EMOCCSVNNXFSDPRCWZBNFIFREJNSJB PDJSFYCCNCYCKANJKPJNLHCDEMQNJE AIQWUOIRSZXUJMEYKYBNWETORGPFLY TIRPUKCAVPAXLHLDJSYUCPCZWRBDVT FQNNPKNMXEOYGKMMWCYQHMXRSYSWKJ IURQPAXJFYYZMANZMCGKUZPOVLHDEK

Output

2397

Test 4 Test

Input

40 XZADHVCOMBACBBHTEYCCXJDNNLMYYDVRQSAOWNOI RZTKUWUMFVHBNEXKYVLQDRUFYAQKNIAIMJKBTGTA EHAOTIYXUEVIQOXLMWTXJTXHNEZIBUQDRHGWTJOV SMNHPIQCWIHIOHQBNMINYYUPKZWHSUFWKUMTENJA VLFBINPJBIIXNHREZHUCUEIXMDOBMRMYYFIGTYEA WRYSXJRQCGWOCBGQQORMTHLRYRQHACUUNRCHIRFV JZBZWXKXMCTICXQALXZKHNXMTGPXXTQMMLHPEHGL TTSURBLRCWGWSTVVELLVTCLJCRKTFSDBAOLGRHHN OQLAKHARLJNJDIYHWSJRETNNZOVXEDOGNFJBPSXT GZSTCXPBKPARDYSQGUUCKCSSPQAIKNVVFIXHWKUK KJIAHTGEOGFBMTCQMZFCZGGTALBHOIZDOAEAVUKX NABDPPDWUGXPMLOFHJBZJFNALQLXWNSPTCEOWDGD ELAECPECRDVSKPUWUECZONMBZONPMZVFJQKCYHLC XTFRWZHKFTZOCHDBVJZPPPHXYVBQEAWBOGEFXYIL JIBXPJDKZPLTINBAOBUBZIUSISQPQZKUXZEGFHVV BGVLWHNHYJNRMTQWWCLDGQVFNSHYDPRESKBWJMBN SUFTWVUHUNNBXLBLVPHFNUADPBZIYOCMMJTOGBRU VXUQTYNINPBJMLHPKFPDVCBYZCAKWASDPJEFYQPP FUOSGBXGUZSODPITUAYOUFGCTYOBQCRCPFQMXFHY JIHWAPIPQEKHFDULYPVKZVEOHWFZQJVKVIGIQRLI DPIWHKRZVKYOEINTAVFMPBXLVYMGDHCSZIQPELHM CJTVHFCMJBOGXWYWAHWXRASNTJFTAXCSJOELOYIN ARCQUIJKAJIPLKQNFTYQZFMMHADTCBPRQQUVJXOV OEUOOYJNXOUNFZWOOSOYCDISWAMEVFYZFTDCFDFG OTQRWRPTUSIKRRYKJVEYGSXQSEGNNPQPVKJJDWDU RBIIAEUNUCRKWZWNRLCBRVBFIOWWDBXLWTMBGFIW UWYVUNGLTPOAUIVZTFDNAVGPZWSVOIZGBDXNFWKF PRNRBRKQTKZPZRPXTJXZCACJFAKTGOVOWRXIQIEY ZEJHECJGTJYSAVCBXLKUCDVIGQQGRXNSCOFZSRZJ RVUJLHKDVNTYXCWGKPPSIWWTSOJXUYVAEVIFOXKH PGLLUAICYQRASURUOGTJNKHAXJLNOGOKXQHQYKRS NSVKBFGQFQHPCPUENNCPNWEEJUGUMVFUVXXFMQBA KTXYSCTFRGDRRFTKRQFDQTLFNFWRDOMVTQLRLIOX BQMCCWRYMHCAMSSRGRPCEPZTYIWAMYQCHSBCAKIM LTURGHLZQJZSTFXPPVBHZKKNAMTYPHCVEBFKBABY JGYXBZRDJEYUCGFYYZLZXBLUKFHMAJYIDKKWFKRE XLLTZANFRHDLEGTCSHWEJYNXNVGXJAJMXPJNVGSB WJQQOLKPVIYUFFEMFOJHTJCWASTILFGGHWUECWAJ HIQTTIUXRSIKZIBXVKMXEKQKBUGFUMEZGZXCBKQE DEHPKLWEXHGMYRYZTGHUAQVIHUZKRTVTARLKCVBN

Output

4832

Validator 4 Validator

Input

40 RIZCYCFHYQGFCJQOOSMMWYSIBRALAZPLDSNLXZBX IWOHWMEIJGFLRLNIVUGWHTVENNZFAUMDAGPNGXCD EZORYVUDOJKWAHXQAHWCWNJIHKSTZPHIELAYIEMZ JYVGWSSCUOMYDFPREUHSRRSDMDYBLMLEKAYTNZFW YWHNNYBMXYUGYDGXGQSUZVQYVDEGQDGERSROQRSC PKQCOAUVSMUXOFYRVVYKWFTIDQBYDLKSLDBBIGHY DPEXRHNOQPCWGQPLEVJRICROKUWECOMDFLKPFOWD CPAGHVHVXKPYIRFEAZJNKOSLEVKIXRYTTHATIERJ HENPMAQIBCIUFGHAPCXUUNBOBDWYLQZGWOVGVCFH BONQPLLAASOWZLRQOJOQCPQFZHOKTGDPTSRPDNPX APJEBLHZXFFYLSSVVTGFXABDCSPFDTYWMIVSOHPP PHOJPQOGMZXHMUFGAGANLLDJMSPPLHRCBHGANQKZ KTFRJWULWERMXWKAKNIUPTSXSBZVABJPYVVKNMWH DGDELIWGROSIXWWQXIJXBCQQOZJNUZQGDFCQZBRR SOJGIAITCYCGOCIPPAOABPHYJWGWKJAUXIZPTLEW RPUXKHPANSAZIPYVDAEYQOBDRRFKBKQLBECWMAQK SWKJKITMYKOVOWXGKIRREEWAQJTFSMPJPGJHGAWK DWCQBPTQNCBMZCYEUAIYABPIOPOSUZMEDDKIDASW KTAUKKDKZWNDHYVXZTRSWLTGJADZPLZLMCESKKMG PSZTKLLPIMIHLTUFFHZPJDSXEXFGUJGFAIJWIWPY ZOFNKEUPCSOFKJBTWXVKNONWRNIMYMKMITYJQZWX KCOWPKEOZZPFMGMSZBMREOCSTVEYBLFRNFPPUOFW XVGTPUGIIROLWJUFTQPFPVZLXVJKZDIEAGJAUJBE DFFVZGQLQXWFDLITZTNJAJRAUBRAYJZVTLAWKKUA XKQZPPKDBSRMUNLYPZUWYZFURDSPBEKKWZNPXNJD QONUHYSLVWKMSNYQGCXZVUQEZIGAXNJFBBSIIWSC YLDZEGGXXBGDQPRWQIKJNVOZUYXCWPPKHMQJFNJB AVLBJVRYHRROSVCXEATEUKLYHVPRTNKRBECUYTTA HETSISDPRCYOZONEJERYRPNGJXXJHSBOAPFVIUWN RYBIKJXRXKMEYAWJJUNUHYUDZUUYOJKFOIULYCTY JFSLJBQOMPPCVSCHMLCCYRYFTAVYNAHOBLZSYZZH DDTJWJCNZKUHKAPBRVUYZKPAMVACOBZDREROGCAJ XKNPWROISNJJHPWXZEKOBQXQNLATYGYIPHZAEZYL GWEIIUGQZGWELYVIDVLZUCBANUVPHDYATRWVZJWW XWZZNHYRWAPGTYNXARRICLSPPSDWFNYBDTMYHXKH EVEPSZMNPUFINFKQETQNXOPTCTYEPDIRKBTBPPCK OWBNLSDSXPZVXTZMEPCQJFYIZLBRGZODJRXAUEDJ FAWTFLHUUBPKMLIWIVSMRMYEKAKVLZMCLTYKSVPF JZANXCSSWYJMRJMCCSFZIIKMCRWUGGDGGCCZMMFM YOSSGXIKVLZNJNAAMMHXUYAMYFMVEVYQANJFGJOQ

Output

4809

Solution language

Solution

Stub generator input

Comments

3 Comments

Velcoro Unnamed CodinGamer

over 3 years ago

I like the idea a lot, but I miserably failed in doing it in 5 minutes. It took me almost 20. So I agree with Zorg1 to have it as a puzzle instead.

Westicles Unnamed CodinGamer

Oh, I thought it was 15 minutes. In that case I agree. I'll switch it to a puzzle, but likely it is too easy.

Zorg1 Unnamed CodinGamer

In my opinion, more a regular puzzle than a CoC. You don't state that water only flows in the 4 directions E/W/N/S (It is generaly the case for this type of puzzle, but I won't say it is so obvious). Some clear testcase miss, to show that the pool can be compartimented with different water level.