Nombre de màxims locals interiors X91360
Donada una matriu de dígits 0,1,2,…,9, hem de comptar el nombre de màxims locals interiors que té. Expliquem a continuació què vol dir això.
Considereu el següent exemple de matriu de dígits:
02139 28124 32453 15321 34173 21771
Fixeu-vos en el 8 que apareix a la matriu. Aquest 8 apareix en una posició interior, perquè està totalment envoltat de dígits. A més a més és un màxim local, perquè tots els dígits que l’envolten (és a dir, tots els que estan a distància 1 d’ell horitzontalment, verticalment o diagonalment) son estríctament menors que ell.
En aquesta matriu, a part del 8, hi ha dos altres màxims locals interiors, que corresponen a les posicions dels dos 5’s que apareixen a la matriu.
Per tant, la resposta amb aquesta entrada és 3.
Entrada
L’entrada té varis casos. Cada cas comença amb dos naturals positius n,m majors o iguals a 3 en una primera línia. Després ve una matriu de n×m dígits 0,1, 2,…, 9 (n línies amb m dígits cadascuna). El cas ve seguit d’una línia en blanc.
Sortida
Per a cada cas, el programa ha d’escriure en una nova línia el corresponent nombre de màxims locals interiors.
Observació
No calen optimitzacions per a superar els jocs de proves privats. Qualsevol implementació més o menys raonable els passarà.
Avaluació sobre 10 punts:
- Solució lenta: 5 punts.
- solució ràpida: 10 punts.
Entenem com a solució ràpida una que és correcta, de cost lineal i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.
Input
3 3 411 071 146 3 3 172 235 051 3 4 4357 2642 3213 4 3 535 563 220 845 5 3 840 544 320 621 599 4 4 3370 4582 3964 0221 11 4 1445 3662 5572 5863 0735 2489 5902 4852 3093 8294 0531 9 5 32331 44591 02206 03978 92001 15892 59002 26221 24220 4 10 3232210980 8262409974 1543623034 7223123105 11 4 3450 4282 0753 3784 7226 6021 4471 1660 9125 3444 7451 11 11 05101114142 15651124542 34476954314 34073126042 46821373559 29595218052 06331792922 31750063474 24506727450 86349296364 15360840515 9 9 205285204 533333532 905599334 502044841 463505635 281825073 019397855 551000493 250495051 4 9 556354922 576453385 230256960 454313201 12 5 40535 52411 32335 40915 94315 32560 26761 18035 17274 63826 05923 58325 10 6 241715 328212 094929 474320 625432 076903 223524 263113 177143 440040 4 9 327540379 586365619 139767382 206152310 9 4 3358 4684 2472 5851 4394 5313 1110 9611 1452 6 3 032 750 880 440 461 552 3 6 425435 254631 533449 7 12 413045415022 700506651996 386577073148 324888892521 501929504970 445782061886 236222074400 9 12 295074511247 092563555507 841567641436 509793442470 912288955352 453912124662 253133377520 146442226137 203011217430 3 7 4020452 6545621 2102004 7 4 3424 0178 1894 4750 2082 6931 2211 3 12 000283032213 105921115444 115400413221
Output
1 0 1 1 0 1 2 4 2 3 10 3 2 3 4 2 1 1 1 5 6 1 2 2
Input
12 11 11011146623 25153578357 26623218783 57332298451 06405493956 26799165643 58219567931 36486444231 45459115269 46646834355 57779734703 22410566562 5 15 520345452124113 232810976724500 949495838780547 225163105989981 145345042320753 15 17 23523846093551531 33029617475919065 57135429632880462 65895287251599725 34052582246111521 34033109093771016 04592603840813274 22165320339951861 44367624905509792 16283872534643441 50369091267006255 28527463083855290 50983345949648444 25405185221295933 01751700555100042 8 20 59431532400215411503 51326665556556665532 58477277073774753641 71532828808518947672 08459390199992237842 53917175123440040210 38842898355444527590 37950432461913634438 7 8 04237320 35750860 48689755 22939284 35554631 53364952 54130454 20 13 6302102023148 3741636952295 0102450930044 5338081586666 2290944075721 4262318883955 3857299792950 7696124793254 3075167841662 2414385092334 4243091234893 4342420419194 1222155321125 2840310285863 7295041269430 3062345731301 5757508636356 2687897954402 0989694316151 0200410031491 19 19 2114532009873531151 2506406029394032387 2377755184630435987 0584821469002524440 3265456738653543645 3277453797034062554 1853278124591757560 4578398906232384860 0099450429436490393 2436366355251055563 0774777716284966742 1281832981957240584 4944610483226998914 2515915912028458913 3960240005393001274 4582140294543431892 1224595508722405294 1696501122981363527 7823024490445425216 19 13 9223443066955 4245542040022 4616669545479 0279751465006 5305823497177 5629691358302 1638682694502 4621715172595 3578589363268 4215903405530 0252915767923 4661601765835 5775328684341 5888629951507 3293935016684 4311616505323 2357371495601 2692998720442 2838034159351 15 17 24434127554211524 01564246562514153 36065575731566635 06597894951357774 50442538635012354 36450990978235654 11254843300947974 93669405543553485 13914324361467232 44085565068780631 36249745315982501 55575500055204395 97794686764592832 54180957227264423 16401134045500537 13 15 055414235302357 586353413649681 079266323007442 228578155491945 396992436048932 120123525746050 432447478101953 443616698998404 209277555231040 185288856334544 264999091207511 254202490282840 394344228794234 18 15 130547081032142 356045929544590 420490344066363 961848936721724 549515153183340 546546476962940 896478876742332 598399391785455 291002010901614 355665621641573 565755672353462 318989238164453 135483525997653 269379033430872 388518055550093 379996964066154 401054524858211 304521710273414 15 8 01927505 11376463 01821764 00496185 25273264 48442235 76236262 28774731 58028502 56506961 06942415 58401265 36999790 41531284 03415501 15 19 5110101711652302405 5045053551656047430 9665653667676786844 0277447087808489720 1888885202353345510 2925994624614666667 1301304144523750800 2044223352011940893 1123507676232519793 4596985638722538584 4171079648026447923 4878508059995785802 3846993215805389094 4455010490634119220 1330033425011324262 7 15 533550252004137 421673556456188 111658643029994 257497977456153 456251802470756 673535425820880 480222032321174 6 19 2565513250338655010 1557065929497976351 2686813430506418760 4229799750379304931 0428156257528194632 3445433425609212954 15 20 22052211523041664143 90546836164572777120 31379141337421888324 14248015356205692141 16395535656767485382 24503267678012964931 36063387148915020532 29762289893933696702 96187344031807274567 20539805949392805388 06429196603006494936 31711220375236205200 13283324318255723632 33952184091911087442 20123327110810341005 16 15 612535270131510 000460704615860 571754202555591 968681219769163 149189588062041 585740395640222 923481160976130 079959550212943 223250033411681 555623963567971 294970547285843 358821989069323 439996989202444 283023951331582 529452636986712 530401822435403 5 16 2115530500903204 2460266205358855 3754701165799730 5643526428441283 0320343531750004 13 19 4415490234041255245 2515355220196960662 3226666660758757013 1474544743951936348 8012398188430432932 2944498902998190684 0026003850834335904 2271999640294962312 4832321546561080444 0236544621754957292 2476137758580423035 0878714396034695400 3104548155545122423 20 13 5545230500500 6665617348591 2771608891174 2388629790056 3145908444123 3641662332365 5625777356743 5678821154544 4609309656600 2124211471754 3852555055185 3691668606063 1102017901050 4457551842667 2688081395553 1199944013661 1435342563492 5562041237835 3760159299013 3351412826770
Output
9 4 23 9 4 16 30 15 17 11 21 6 15 5 9 24 19 5 22 15
- Author
- PRO1
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++