| Бодолт илгээх | Бүх бодолтууд | Шилдэг бодолтууд | Жагсаалт руу буцах |
RGB7904 - Cow Beauty Pageant |
Hearing that the latest fashion trend was cows with two spots on their hides, Farmer John has purchased an entire herd of two-spot cows. Unfortunately, fashion trends tend to change quickly, and the most popular current fashion is cows with only one spot! FJ wants to make his herd more fashionable by painting each of his cows in such a way that merges their two spots into one. The hide of a cow is represented by an N by M (1 <= N,M <= 50) grid of characters like this: ................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... .........XXX.... Here, each 'X' denotes part of a spot. Two 'X's belong to the same spot if they are vertically or horizontally adjacent (diagonally adjacent does not count), so the figure above has exactly two spots. All of the cows in FJ's herd have exactly two spots. FJ wants to use as little paint as possible to merge the two spots into one. In the example above, he can do this by painting only three additional characters with 'X's (the new characters are marked with '*'s below to make them easier to see). ................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. ........XXXXX... .........XXX.... Please help FJ determine the minimum number of new 'X's he must paint in order to merge two spots into one large spot.
Input
Input description...
Output
Output description...
Example
Input: etc. Output: etc.
| Нэмсэн: | Bataa |
| Огноо: | 2013-12-18 |
| Хугацааны хязгаарлалт: | 1s |
| Эх кодын хэмжээний хязгаарлалт: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Програмчлалын хэлүүд: | ADA95 ASM32 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE |
| Эх сурвалж: | USACO 2011 November Contest, Bronze Division |
hide comments
|
2019-12-26 13:01:46
Хамгийн сүүлийн үеийн загварын чиг хандлага нь арьсан дээр нь хоёр толботой үхэр болохыг сонссон Фермер Жон хоёр цэг бүхий үнээний бүхий л сүргийг худалдаж авав. Харамсалтай нь загварын чиг хандлага маш хурдан өөрчлөгдөх хандлагатай байгаа бөгөөд өнөө үед хамгийн алдартай загвар бол ганцхан цэг бүхий үхэр юм! FJ нь үхэр тус бүрийг хоёр толбо болгон нэгтгэн будах замаар сүргээ илүү загварлаг болгохыг хүсч байна. Үхрийн арьсыг N нь M (1 <= N, M <= 50) тэмдэгтүүдийн сүлжээгээр дүрсэлнэ: ................ ..XXXX .. ..XXX ... ... XXXX .... XX ... .XXXX ...... XXX .. ........ XXXXX ... .......... XXX .... Энд "Х" нь цэгийн хэсгийг илэрхийлнэ. Хоёр 'X нь тэдгээр нь босоо эсвэл хэвтээ байдлаар байрладаг бол нэг цэг дээр харьяалагддаг (диагональ зэргэлдээх газар нь тооцохгүй), тэгэхээр дээрх зураг нь яг хоёр цэгтэй байна. FJ сүргийн бүх үнээ яг хоёр толботой. FJ нь хоёр толбыг нэг дор нэгтгэхийн тулд аль болох бага будаг хэрэглэхийг хүсч байна. Дээрх жишээн дээр тэрээр зөвхөн гурван тэмдэгтийг 'X' тэмдэгтээр зурах замаар үүнийг хийж чадна (шинэ тэмдэгтүүд нь үүнийг харахад илүү хялбар болгохын тулд доор нь * * 'тэмдэгтэй тэмдэглэсэн болно). ................ ..XXXX .... XXX ... ... XXXX * ... XX ... .XXXX .. ** .. XXX .. ........ XXXXX ... ......... XXX .... FJ-т хоёр цэгийг нэг том цэг дээр нэгтгэхийн тулд зурах ёстой 'X' -ийн хамгийн бага хэмжээг тогтооход тусална уу. Байна. Khamgiin süüliin üyeiin zagvaryn chig khandlaga ni arisan deer ni khoyor tolbotoi ükher bolokhyg sonsson Fyermyer Jon khoyor tseg bükhii üneenii bükhii l sürgiig khudaldaj avav. Kharamsaltai ni zagvaryn chig khandlaga mash khurdan öörchlögdökh khandlagatai baigaa bögööd önöö üyed khamgiin aldartai zagvar bol gantskhan tseg bükhii ükher yum! FJ ni ükher tus büriig khoyor tolbo bolgon negtgen budakh zamaar sürgee ilüü zagvarlag bolgokhyg khüsch baina. Ükhriin arisyg N ni M (1 <= N, M <= 50) temdegtüüdiin süljeegeer dürselne: ................ ..XXXX .. ..XXX ... ... XXXX .... XX ... .XXXX ...... XXX .. ........ XXXXX ... .......... XXX .... End "Kh" ni tsegiin khesgiig ilerkhiilne. Khoyor 'X ni tedgeer ni bosoo esvel khevtee baidlaar bairladag bol neg tseg deer khariyaalagddag (diagonali zergeldeekh gazar ni tootsokhgüi), tegekheer deerkh zurag ni yag khoyor tsegtei baina. FJ sürgiin bükh ünee yag khoyor tolbotoi. FJ ni khoyor tolbyg neg dor negtgekhiin tuld ali bolokh baga budag khereglekhiig khüsch baina. Deerkh jisheen deer tereer zövkhön gurvan temdegtiig 'X' temdegteer zurakh zamaar üüniig khiij chadna (shine temdegtüüd ni üüniig kharakhad ilüü khyalbar bolgokhyn tuld door ni * * 'temdegtei temdeglesen bolno). ................ ..XXXX .... XXX ... ... XXXX * ... XX ... .XXXX .. ** .. XXX .. ........ XXXXX ... ......... XXX .... FJ-t khoyor tsegiig neg tom tseg deer negtgekhiin tuld zurakh yostoi 'X' -iin khamgiin baga khemjeeg togtookhod tusalna uu. Baina. |
|
|
2019-01-30 13:28:20 B.Bayardalai
Бодсон нь орчуулж өгөөч |
RSS