JOIN
 Problem Statement
Contest: Marathon Match 66
Problem: DigitsPattern

### Problem Statement

A pattern is created by filling cells on a square grid with digits. A freshly filled cell gets a value of 1, and the four cells adjacent to it (vertically or horizontally) get +1 to their values if they are already filled. Thus filling the same cells in different order creates different patterns of values.

You are given a String[] targetPattern that you want to create. targetPattern[i][j] will be '.' for cells which can't be filled, and digits '1'..'5' for cells which should have a value in them.

Your task is to return the sequence of cells to fill in order, so that the resulting pattern is as close to targetPattern as possible. The "distance" between patterns is defined as the sum of absolute values of differences between values in the same cells. Elements 2*i and 2*i+1 of your return represent row and column of the cell that should be filled i-th. All cells in your return must be distinct. You can fill only the cells of the pattern marked with '1'..'5', and you must fill all of them. Thus the number of elements in your return should equal 2*(number of '1'..'5' cells in targetPattern).

Your score for a test case will be the "distance" between targetPattern and the pattern obtained by filling cells in order of your return, increased by 1. Your overall score will be calculated as follows: for each test case you get 1 point for each competitor you beat on this test case (i.e., your score on a test case is less than this competitor's) and 0.5 points for each competitor you tie with (a tie with yourself is not counted); finally, the sum of points is divided by (the number of competitors - 1). Invalid returns are given score of 0.

The test cases are generated as follows. The number of columns W and rows H in targetPattern will be chosen between 10 and 100, inclusive. Then, between 10 and 30 random diamonds of '?' characters are placed on the grid. A diamond with radius w0 centered at (i0, j0) is a group of cells (i0+i, j0+j) for abs(i)+abs(j)<w0. A diamond can be partially outside of the grid. Finally, all '?' characters are replaced with '1'-'5' characters in one of the following ways (chosen randomly with equal probabilities): either all cells are given random values, or they are filled using the same process as used in your return, with cells filled in random order.

A visualization tool is provided for offline testing. It also allows manual play.

### Definition

 Class: DigitsPattern Method: recreate Parameters: String[] Returns: int[] Method signature: int[] recreate(String[] targetPattern) (be sure your method is public)

### Notes

-The memory limit is 1024 MB and the time limit is 10 seconds per test case (which includes only time spent in your code). There is no explicit code size limit.
-There are 10 example test cases and 100 full submission test cases.

### Examples

0)

 ```seed = 1 H = 10 W = 10 targetPattern = .232.24313 .134123332 ..1..31513 .2....413. 222..23251 1351251413 4335422352 1414233414 4251243..1 212332.... ```
1)

 ```seed = 2 H = 50 W = 23 targetPattern = ....................... ......................4 .....................51 ....................115 ...................5233 ..................51544 ...................2453 .5..................515 543....2.............34 5452..342.............4 331..51244.........3... .5....215....5......... .......2....532........ .............2......... ....................... ..4.................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....................... ....2.................. ...212................. ..45234................ .2342324............... 135143325....2...5..... 5344233555..532........ 434311252.542323....... .4222521.54214315...... ..25322.4423153133..... ...113...35132414...... ....4.....235545....... ............322........ .............4......... ....................... ```
2)

 ```seed = 3 H = 29 W = 99 targetPattern = .213...............2412533......124412232252544......4413233251233224....15343..1222434............ ..2...............353433323......4451311152235......4535353251552354....1355122342551544........... .................52424322532......11233333335........5314241..42313....324134535151225541.......... ..................353222151........134432215..........43522....232....24545522134331343551......... ...................1514434..........2132233............152......1....1533225234112231344432........ ....................3.151.........4..34343..............5...........2244554153134241334245......... .......................1..............413..........................5553324355245343312214.......... ...3...................................4............................42431151241455443123........... ..253...............4................................................443352443533413523............ .35242.............531................................................2434542522213424............. 1525452...........41342................................................331433523..232.............. 33554141.........1142244................................................1312541....1............... 222241424.......315423513................................................55121..................... 5412243143.......2321434....................................4.............143...................... 43441421344.......32544...................1................141.............5....................... 533351343315.....5535515............11...151..............33344.................................... 35213411545.......23423.............141...3..............5154221................................... 2542411431.........131.............31414................343112113....................4............. 531211543...........1...............151................22443522521..1...............315............ 34421225.............................3..................422321355..141.............31545........... 2243253..................................................2222451..42213...........1555232.......... .22144....................................................42235..4134331........1435115325......... ..244......1...............................................351..213241142......1144533213.......... ...2......415...............................................2..25435132424....1124234535........... .........25415..............5...................................144331435....4142322512............ ..........454....................................................4324334....1452421555............. ...........2.............................1........................31245......4145441............... ........................................354........................522........35341................ .........................................3..........................3..........143................. ```
3)

 ```seed = 4 H = 83 W = 52 targetPattern = ............................................14212... .............................................143.... ..............................................1..... .................................................... .................................................... .................................................... .................................................... ......................................1............. .....................................223............ ....................................25423........... ...................................3242133.......... ..................................141254123......... .......................2.........33334313521........ ......................213.......2152151351441....... .....................15412.....135152435235252...... ..............1.......223.....32525151241431423..... .............233.......1.....2143225325151542221.... ............21521...........145151513343141235343... ...........1344423.....2...15214144415242533512413.. ..........225131523...123.1513542431341531432541413. .........25242442412.1352151353151235151435221254412 ........12351351314523532442531342352514513432513143 ....2..235125415333251315315324522513152322534244514 ...2142141541431415142543152123335135413534253223351 ..25233525135153451515131415333153242151253133151232 .212451352431521315141532523515413242513442414522344 2435215321245245432353354141252144354152431541245422 151233235423321425144221423451454312251421513452122. 23235443224134513341342422334341413532452515132443.. 4435314324524323142351352452242432515122424145123... 3241352123235244251422532334141533141524525422351... 22241425414531425153542253145143152541522141441251.. 313541531324135125131342232422515143332444254235133. 4253152152523425413451543241531335152251521421414521 15225154243422341351253141.2235432525134153134351424 2352353322525153351453323...243221341542515335135252 424124131331441413532414...1542543124142241251512313 123452443353223151412333..14231232435432543243133452 2513413515152423351525131..2514434142131325315245142 43331513524435252251514531..223451535253523443312512 322351514132315242151431441..31244314234212521535152 214324132531451245315413525325331325252253515231242. 424515245335223432531435313312.3441413514133233531.. 251432413312452235252424135133..1351324415431351541. 2222515225351325241251313522452..1434322531425144142 25431514512345131235145431541341..315413432522531341 4124515142423145434224225231413232324235214134314453 2351331515432412425432421443535253152151524454151313 3143532241351525133151532251222515243415242212434423 4313153453223352351515253425335153225141523543134251 1524321243315131532334132514152512452335214124514142 4145323525424235224152251442521435321533244542245324 2413534134151352415224415132134124143251413344123512 1441415223224522352245141445345341..321453214244123. 342515143535231343351344231314151....2521532321542.. 15135225213135252514421525335251......15325244512... 2432243143542242343415314215312........214142423.... 414415435142154214133133525213..........2535231..... 13522331251533134134534424152............22213...... 3524453332524133.25142151441..............252....... 141242144131442...141341513................1........ 41541541425251.....2525413..............1........... 2431532345252.......15213..............151.......... 3214131514141........152..............25143......... 43254251514133........1..............3124123........ 152423252235412.....................124244522....... 32525412435142.....................33325222512...... .131414542142.....................3145424151452..... ..3415131431.....................215243254252212.... ...151..252.......................3221313212542..... ....1....1.........................33242543512...... ....................................324521313....... .....................................3124433........ ......................................24521......... .......................................222.......... ........................................2........... .................................................... .................................................... .................................................... .................................................... .................................................... .................................................... .................................................... ```
4)

 ```seed = 5 H = 59 W = 83 targetPattern = ..........................22214324355....5544334431541531535445112................. .........................1322423421245..554211212422155523423532223................ ........................12134354224512541515121341144425544453434335............... .......................4111554524353551122541443514114323134223231244.............. ......................415445442335435245423115435111521142255444145145............. .....................13551143121315114115432413113211353335424523533321............ ..................3.14345544312313521124112141125311131332343211412231.4........... .................412.324433124532145343413523224231431152121434355232.115.......... ................12134.5554531332552422411552223141114552344453323235.24444......... ...............2421454.43141224152435113413141352353333214451523144.1341254........ ..............425355444.221153431321134311145513341443224133155551.152421213....... .............32551231524.3322435451354442412244511351533213455213.31155321432...... ............3244551235443.35254552314211151453411552314313124231.3511544453524..... ...........112422122351154.222124553255342342542333555422215252...44214143415...... ............34133553535434..5322344125134212522253515424223443.....123422344....... .............22124314411121..4254212345332443533213212323245514.....5432451........ ..............34412225323142..155.123553431331513454224334552315.....15554......... ..............112413514535114..4...423253414334241324551355435552.....132.......... ...............4325321234145........5543214435243345235331543134.......2........... ................41343245153..........445455152344225231151555151................... .................454512513............111444252541541212534551543.................. ..................4122522..............134533535534221232425453454.4............... ...................41222................44533433413553144242241525533.............. ....................341..................12221111244335245215524322514............. .....................2.....................4314453444153141125522253555............ ............................................5212335354133254131452235555........... .............................................5232154544244352432411311345.......... ..............................................5125214355414523254541534224......... ...............................................3..2344233515225414134352223........ ...................................................4515313141323331125211554....... ....................................................4345331244135133443515444...... .....................................................4252524133325351424422412..... ......................................5...............2523541531345315251441331.... .....................................442...............4245553353535122513315553... ......................................5...............515354213412352133412255441.. .......................................................4345335431251214533335241... ........................................................22125314325532325321521.... ............4............................................325325125411131252213..... ...........415............................................1214524343354522511...... ..........13315............................................54345515522441122....... .........2211532...1....................2...................423234115522242........ ........554135553.354..................551...................5411335152341......... .........3415155.21533................41543...................33555552145.......... ..........54423.3524242..............5235324...................513222553........... ...........313.425243525............544521244...................3515121............ ............3.22554351551..........52132241531...................22253............. .............3125534113412........3315432325413...................252.............. ..............55122543214..........25212534243.....................1............... ...............215423542............413455144...................................... ................3513141..............5111211....................................... .................11215................43213........................................ ........3.........113..................124......................................... .......411.........2....................5.......................................... ......24355...................................4.................................... .....3454221.................................334................................... ......14533.................................44425.................................. .......245...................................312................................... ........1.....................................5.................................... ................................................................................... ```
5)

 ```seed = 6 H = 36 W = 34 targetPattern = ........154342253434112552515545.. .......21234534534144425122135415. ......1222252432423211144153512214 .....11312433214332452515444344432 ....141444445152553354311553533231 ..21213143442412221243451515312413 .335515555355243124321345522322442 5231421444351125443142425411541411 .23155112532521435.152145554444154 .32..2235431123244..35351222515534 335...1212554432552..2521142515333 1343..12223334535251..45341423555. 53124334131244234412543312125124.. 3122125134141252143543521341512... 31444313114254134112325531245222.. 232523113533133235214211553211545. 5245225552515152345241451423342121 5125512551323442541514251255215455 1132122223443322344354112452324223 2323514222541541154554235522545315 3451453234432221511145125111551243 1124115513242343211354152133214251 2321352441542253143444351434534251 5252441143534353241421451435124551 .543225425353142111314532335515515 ..31321342123135323343314514315313 .544151433415511255224143442323433 .445253121341344133332442211155231 4512431451241324423351351442333241 .151312231525453121522242341553413 ..2512331114332133135253.351542212 ...3152523343255451534415.12122555 ....5132341155343242311415.3521432 .....1221143225533311422131.121445 3.....5111443254514521522442.25325 .......22535242252442141423...3235 ```
6)

 ```seed = 7 H = 54 W = 98 targetPattern = ...................1455531543213134415112153423111533521133335343...13321435421145511153232113.... ..................335512445235315423444143152544411224434522441423.4354524352135132312232253452... .................1342211541311254434232112224351231145244131155435115345313333242352242221543453.. ................312343411452115212413531525235555234255435335235441244421251135333545511521444252. ...............12534141522355314144352132434255311113534452122444.34324151321445132421332242411423 ................331345232411351534455513314531114352443151243445...551522255454541331352455222243. .................2453541334313351553324314513142121335142241345.....411434345213444354513215252241 ..................24155344214155344243445321335244431441455155.......22321155423243311434243313351 ...................422541352112554214431535545334311322322555.........232335354352552..35245152434 ....................1455114225343143252521115345312355432243...........1153151145414....2413223244 .....................33144125142333145422121414251233133544.............3213433115513....541353351 ..1...................234554142543242131152341232323531422.............443531515154453..4154351325 .512...................2512512551523135244..5431334414235.............1321224325211211122441342531 33322...................41553223234454542..4411513335213.............11111312242145211242232544214 535522...................233533541341532..5114515235345.............523313211123145212144234134352 2235211...................2211133325314..4323431245511.............5322531311443451353551154533423 54115451...................43133155112..154321433124533.............342125254345113125554..2545312 332511334...................3233413321.32321231532223145.............5553125213451444352....113141 1242554235...................5324114553321442323533234533............325112235321154211....5133345 12153134515...................4523522124421233512153522141..........352445544455455421....44142411 415134111115...................2312115545224515324134533152........114425214311124132....244513123 2542553324534..................114533143425352243214123432........154342232412342343....2344255111 55433233421542................145254554223554523134515324........215215553414333121....31435223253 135343352225311..............254153324231415322215114115........432353121214122544....444552135535 3522231515255223.......2....214554121125445351514152552........521232232123114323....5231454121512 13354342451251145.....151....1235235342111313341221345........414455543331431111....33542414535224 125452235123454113...33125....31334524434151325512343........121232541512412454....311435411511141 2511512334442222424.3415214....15443414415.241122433........1511532424142533342...4331132235541211 142512223451254522...25235......243554313...3335154........432152434423531212332.43545552523115352 55434241421435424.....252......4.4242343.....24531........5341531314211354531315233541451211553123 4344521514512442.......2......521.32323.......233........55312152531454355211121131454532552342312 212333253441425..............42535.535.........3........541331414124521231435541234113551324545333 53541345541354..............3453153.4..................4243252441215412113153431425422544425541122 1533435322154..............321311123....................514231545251551413313252532445512355412422 434435335523.4............45524341412....................4231341545133224533351351.121345213432434 54223123541.114..........2524324244415....................3445444441453554414235232542221545345541 5111315551.54551........551151314122545....................452432354452253523213544534311232225255 553245254.1323123......45442551321335353....................32544435141121453532211541225544143222 122412421135532251......525121244314254......................1153555131243544111335244424224421231 2342441522213342234......4115242344313........................45353535245521451352322431423152535. 33411444153553151443......12225153454..........................531553444215443253223133335122532.. 254141142234352252315......255423351............................2434512535244323153312435144453... 3313323455442544235421......1431352..............................5221155531141344155542245.555.... 14512511433325521213335......21244................................43534153325212214234532...5..... 541233545213211532543414......151..................................242343211125335234214.......... 2253155443125235542525112......2....................................2413444145224132244........... .5523455522122244223444453...........................................1.153125334231433............ ..44213231345222123513215...............................................2114113455255............. ...431313151132213122321.................................................21141251332.............. ....3234355513242312353...................................................432223233............... .....44334325445234325..............5......................................2125124................ ......125543442545134.......................................................13443................. .......5342153232115.........................................................551.................. ........25233415233...........................................................3................... ```
7)

 ```seed = 8 H = 30 W = 49 targetPattern = ........2.212324141.....24123........221423412242 .......3123435123433...3215413......1544141235313 ......142541515334322.315312413......221525442541 .....141441425134221513515353431......33312432343 ....33351251524154331512332325243......4145321422 ...2315325223514325424234521441421..1.32233154124 ....15333154232421333354134513313..14424515412541 ....2431531415245314143151234532..232224252145313 ...1522514525251245443151453123..1445142135314153 ....15143331223541322341432152..25221534523342522 .....144151533241441351342522..223435214313451251 ....14215141515141..313..142..1513521542141243514 .....34313..15252....2....1.314252154124534513341 ......133..1.222......1....1345135421452213151513 .......2..252.1......322..33133413435213425243353 .........14131......12452125315251423523451531322 ........3324532....135143252442235221443135124313 ........252212....1351514421344213534425241534453 .......22154423..24524245243351442322321.24231323 ........3532252432141523315123441521433..15254312 ........124152142541341514225152335224..323123524 .......2352514331225313324431425212522.2135251351 ........12223415434244254145431344523...252415142 .........325253131515143153125432341.....24141532 ..........23433..235235144135131232.......1542413 ...........122....1224152243154251.........21523. ............2......32452135423351...........312.. ....................323334125212.............2... .....................151..25152.......1.......... ......................1....141................... ```
8)

 ```seed = 9 H = 74 W = 55 targetPattern = .........22142354552144434452455513423................. ........25531435334552154544413123343.................. .......322242155232333525452243233322.................. ......34331534441414531131511524122511................. .....2425355122255124352231343352241251................ ....233455134245543453134224135152321334............... ...52121545211345232232152215424333125533.............. ...145153311344332444535413243551253453255............. ..32451223333533214552341134331145215525411............ .4433544432351243232221114433423142233422452........... 5421455542133111314341253345144324434322223............ 154244235224234445143453255121143533524525............. 41154422443133145124134534113433242321231.............. 5433154143521332341451353413115313521551............... 3114255555424511253554415125243335424343............... 25544313525141432535411541324253134233334.............. 4535244452115535233111444141214154351254............... 114233315254133425522532213212422132113................ 54315332343313243312255555434431332323................. 3313312342354414111115254323221353354.................. 441455532454555135431341145431525412................... .1534524315442525433225455112235111.................... ..13221453144443442133..2251213145..................... ...551124252212314253....41235331...................... ....515151242225524.......543344....................... .....2214352213232.........1224........................ ......35343442314............2......................... .......252213152....................................... ........5433131................2....................... .........25354............5...321...................... ..........332............455.43144..................... ...........2............15433531213.................... .......................1135122441325................... ......................515415243543312.................. .......................411552253145233................. ........................513222413554535................ .......................55212332213353221............... ......................4345512343343235441.............. .....................423134535114132212542............. ....................12342141154511254255133............ ...................2335252213525412212124354........... ..................313335555423111454435114435.......... .................25342551432332245515125444554......... ..................333431121532521423441551334.......... ...................3514335123221241433413523........... ....................34533212243221413231331............ .....................2124111311212445353533............ ......................4431122443422442554315........... ......................43545512324231545524215.......... .....................1545244221325244343111235......... ....................122531451152125334445442243........ ...................21111313112354453224434241245....... ....................122544312512331145335533311........ .....................4244551231154411255234442......... ......................23142..5513221554542331.......... .......................114....235..451355412........... ........................2......1....3131552............ .....................................14122............. ......................................144.............. .......................................3............... ....................................................... ....................................................... ....................................................... ....................................................... ....................................................... ....................................................... ....................................................... ....................................................... ....................................................... ....................................................... ....................................................... ....................................................... ....................................................... ....................................................... ```
9)

 ```seed = 10 H = 41 W = 84 targetPattern = 2414131422........2142342324141313212..142........2214222.1331421................... 13332452422......24241222351532524335244133........25313.251541523................1. 441531315151....2135134352142142452531424313........123.21333431521..............332 3223454415151....2515351253533151413152151512........2.2535222432541............3251 14514131513441....2231353213534224242253334351........213131435413151..........22313 313243351532423....2524252432152514453315322251........4335424224451......2...145153 2354151423522512...33431351444141414151513425142......3151241515212......313.2243231 24134152313153351.33321413514245335251514321251......3151451335232......124124341453 3541531444542132.31513454213512415313525325331......2431512451433......1445244124141 331434513423531.1252353134251451341.141354252......3125243523522......25221515242423 32513214132213.32514212515315214532..1524322......1245252331312......213444143345414 3125443335342.315144534132531441414...22241......13512331244.2......1541521413532241 154313153123.31435312242542352541322...321......1541352442332......13315152541341543 41314251452.2152142342451315231233523...2........21533153232......234523335315124331 2452541431.245332431531335324143542441............325142251......1521254141241451524 213531513.22131451523535134144252223232............1334142........225223513532415313 .3224432..442524141531343522531314544152............14522..........31352244335151322 ..14131..32241515253151412353153414125133............123............2531532351515434 ...333..2415342514415331454315151532514132............2..............215313123423312 ....1..122431512323522541422524442152252512...........................32142525325133 ......154425425324125141532513312531542413.............................2445342142234 .....134131423233453153243135153525343152...............................124124542443 ....335235234124522443134241241231423431....................2..........2541452215141 ...142125151535135125144125434454421323....................221........22422414351414 ..231353251514141432241533343124242513....................25252......152154225314531 .235244153324245224445415214144321513....2...............3134132....232423254235224. 252242151331252135212325143142515342....231.............315153512..14315352213131413 122533233532333524353421..335135131....24142......2....13335213543235434143423334531 42324535123535125313532....1432333....3154151....212..341431524222152213514135252243 1353413223512424425131......12323....134415152..14251413351515135331525143344133521. 252223442334224131252........323....1512423421413531324431515144135324252525134223.. .2314525352443525251.......2..2....2314514145342515344521432241524241521341245331... ..25142131252235222.......321.....2533324442412424412244252345223515425423352143.... ...141423523141352.......21451...3125152521242432134234153133244525231241252422..... ....3353514524332.........312...1425242124541454431525152145314221315242432152...... .....14215324412...........2...25231415253132243145322435413542542432451..241....... .....4134141513...............31344544151244251251314524215131243254122....2........ ....2243541513...............21421414141541542534253141254143442141243.............. ...1521421513.................245433145241432341251341352334141444541............... ....143..313...................2212543151541312451453253151525414212................ .....1....2.....................24313133231342421412432141413314133................. ```

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.