Problem B
Orientering
Languages
en
sv
Hanna håller på och anordnar en orienteringstävling. Hon har redan bestämt att banan består av ett rutnät som är $N \times M$ rutor där varje ruta innehåller en kontroll som är en bokstav. Alla deltagare kommer att starta i rutan i översta vänstra hörnet och slutar i det nedre högra hörnet, dessutom får de endast springa åt höger eller nedåt. De får alltså välja själva vilken väg de vill ta och kommer totalt att besöka $N + M$ kontroller. Deltagarna fyller i bokstäverna de hittar längs vägen och lämnar sedan in sekvensen som uppstår till domarna som ett bevis på att de verkligen har besökt rätt antal kontroller. För att garantera att ingen fuskar och följer efter någon annan vill Hanna se till att inga deltagare springer samma väg, det vill säga att inga deltagare lämnar in samma bokstavssekvens. Det kan dock uppstå problem ifall det skulle vara så att två olika vägar genererar samma sekvens – då kanske oskyldiga deltagare anklagas för fusk. Nu vill Hanna ha din hjälp med att kontrollera om det finns vägar på banan som genererar samma sekvens.
Indata
Först kommer en rad som innehåller talen $N$ och $M$ ($1 \leq N,M \leq 2\ 000$), där $N$ är banans höjd och $M$ är banans bredd. Sedan följer $N$ rader där den i:te raden innehåller en sträng med längd $M$, där en sträng är en rad i orienteringsbanan. Alla bokstäver som förekommer är mellan ’a’ och ’z’. Inga bokstäver är versaler.
Utdata
Skriv ut ”Ja” om det finns två vägar med samma bokstavssekvens och skriv ut ”Nej” annars.
Poängsättning
Din lösning kommer att testas på olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$20$ |
$N = 2, M = 2$ |
|
$2$ |
$20$ |
$N = 3, M = 3$ |
|
$3$ |
$20$ |
$N \leq 10, M \leq 10$ |
|
$4$ |
$40$ |
Inga ytterligare begränsningar. |
Förklaring av exempelfall 1:
I det första exempelfallet spelar det ingen roll vilken väg man tar, man kommer alltid få sekvensen "abcab". Därför finns det flera vägar med samma bokstavssekvens, och svaret är därmed "Ja".
Förklaring av exempelfall 2:
Alla vägar genererar olika sekvenser, därmed är svaret "Nej".
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 abc bca cab |
Ja |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 3 bfd ash cbn abs |
Nej |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 5 bvjad vsahi jncbu ausug diugy |
Ja |