Problem E
Räkna öar
Du ska skriva ett program som räknar ut hur många sammanhängande öar det finns på ett sjökort. Sjökorten representeras av en textsträng med tecknen ‘$\sim $’ för vatten, och ‘@’ för land. Givet ett sjökort som indata ska ditt program returnera antalet fristående öar som finns på kortet. Två @-tecken anses tillhöra samma ö om de angränsar till varandra rakt i sid-led eller höjdled (diagonaler räknas alltså inte).
Input
Alla indatafiler inleds med två tal, $x$ och $y$, där $x$ anger hur många rader som sjökortet har, och $y$ anger hur många tecken det finns i varje rad. Du kan anta att $1 \le x \le 10\, 000$, och $1 \le y \le 10\, 000$. Du kan också anta att alla öar är helt ifyllda, dvs det finns inga öar som innesluter sjöar som inte är förbundna med det omgivande havet.
Output
Ett heltal, som anger antalet öar.
| Sample Input 1 | Sample Output 1 |
|---|---|
8 13 ~~~~~~~~~~~~~ ~@@~~~@~~~~~~ ~@@~~@@~~~~~~ ~~~~~@~~~@~@~ ~~~@@~~~@@@@~ ~~~~~~~@@~~@~ ~~~~~~@@@@~~~ ~~~~~~~~~~~~~ |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 10 @@~~~~@@@@ ~@@~~~@~~~ ~@@@@@@@@@ ~~~~~@~~~~ ~~@@@@~~@~ @@@~~~~@@~ @~@@@@@@@~ @~~~~~~~~~ @@@@@@~~@@ ~~@@@@@@@@ |
1 |
