Problem F
Hitta Stigar
I den här uppgiften ska du skriva ett program som kan läsa in en karta, och sedan hitta stigar som förbinder två sidor av den. Kartan består av en matris med M rader och N kolumner, innehållandes bokstäverna A-Z. Programmet ska skriva ut alla bokstäver (i bokstavsordning) som förbinder kartans översta och understa rad med varandra via en eller flera stigar. Två rutor i kartan anses tillhöra samma stig om de ligger antingen direkt ovanför/under, eller bredvid varandra. Inga diagonaler räknas alltså.
Om det inte existerar några stigar alls, ska programmet skriva ut "0" (en nolla).
Notera att stigar kan förgrena sig, alternativt att det kan finnas flera giltiga stigar med samma bokstav, men svaret ska bara innehålla samma bokstav högst en gång, oavsett hur många giltiga stigar som finns med den bokstaven.
Indata
I indata anges först två heltal, som anger antalet rader (M), resp kolumner (N), i den ordningen. På raden därefter följer själva kartan, som M rader med N tecken i varje rad.
Du kan anta att N och M är heltal, och minst 1 och högst 10 000, samt att kartan består av versaler.
Utdata
Enn sträng av bokstäver i alfabetisk ordning, eller siffran 0.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 6 AACACD ABBABD ABAAAD ABABAD AAABAD BBBBBD |
D |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 10 ABCDEFGHIJ ABCDEFGHIJ ABCDEFGHIJ ABCDEFGHIJ ABCDEFGHIJ ABCDEFGHIJ ABCDEFGHIJ ABCDEFGHIJ ABCDEFGHIJ KKKKKKKKKK |
0 |
