(* Camelot (IOI 1998) Copyright (C) 2000 Sebastiano Vigna This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Il problema viene risolto prima di tutto implementando un semplice algoritmo di calcolo del numero minimo di mosse per raggiungere una posizione. Il calcolo avviene per diffusione con scansioni globali successive (e` semplice da implementare e sufficientemente efficiente a causa della limitatissima dimensione delle scacchiere. Quindi le matrici delle distanze vengono combinate in vari modi cosi` da simulare i vari comportamenti possibili (nessun incontro, incontro con il cavaliere i per ogni i). *) {$R+} function min(a,b: Integer): Integer; BEGIN if b data. Inizialmente riempiamo la matrice con oo (infinito), e inizializziamo la posizione specificata con 0. Scandiamo la matrice alla fase d>=0 alla ricerca di elementi che hanno distanza d dalla posizione iniziale, e minimizziamo la distanza degli elementi raggiungibili dall'elemento trovato con d+1. La matrice delle mosse viene passata: in questo modo possiamo utilizzare questa funzione sia per il re che per i cavalieri. *) PROCEDURE distmin(VAR M: distanze; x, y: Integer; mosse: listamosse); VAR i, j, k, d: Integer; fine: Boolean; (* Funzione di comodo per controllare se una posizione sta dentro la scacchiera. *) FUNCTION dentro(x, y: Integer): Boolean; BEGIN dentro := (x>=1) AND (x<=DIM) AND (y>=1) AND (y<=DIM) END; BEGIN d := 0; FOR i:=1 TO DIM DO FOR j:=1 TO DIM DO M[i][j] := High(M[i][j]); M[x][y] := 0; REPEAT fine := true; FOR i:=1 TO DIM DO FOR j:=1 TO DIM DO (* Scandiamo la scacchiera *) IF M[i][j] = d THEN FOR k:=1 TO NMOSSE DO (* Scandiamo le mosse possibili *) IF dentro(i+mosse[k][SX], j+mosse[k][SY]) AND (M[i+mosse[k][SX]][j+mosse[k][SY]] > d+1) THEN BEGIN M[i+mosse[k][SX]][j+mosse[k][SY]] := d+1; fine := false; (* Se abbiamo aggiunto qualcosa dobbiamo continuare! *) END; d := d+1; UNTIL fine; END; VAR c, d: Char; i, j, k, p, q, rex, rey, ncav, mosse: Integer; F: Text; BEGIN ASSIGN(F, ''); RESET(F); (* Il re c'e` sempre *) READ(F, c, d); rex := ord(c) - ord('A') + 1; rey := ord(d) - ord('1') + 1; (* Andiamo ora a leggere due caratteri per cavaliere. Alla fine ncav conterra` il numero di cavalieri. *) ncav := 0; WHILE NOT EOLN(F) DO BEGIN READ(F, c, d); cavx[ncav+1] := ord(c) - ord('A') + 1; cavy[ncav+1] := ord(d) - ord('1') + 1; ncav := ncav + 1; END; (* Costruiamo le matrici delle distanze. *) distmin(Dre, rex, rey, mosse_re); FOR i:=1 TO NCAV DO distmin(Dcav[i], cavx[i], cavy[i], mosse_cav); (* Prima fase: sommando in T tutte le matrici si ottiene una nuova matrice che rappresenta, per ogni cella, il costo di radunare li` tutti i pezzi _senza incontri_. *) FOR j:=1 TO DIM DO FOR k:=1 TO DIM DO T[j][k] := Dre[j][k]; FOR i:=1 TO ncav DO FOR j:=1 TO DIM DO FOR k:=1 TO DIM DO T[j][k] := T[j][k] + Dcav[i][j][k]; (* Ora troviamo il minimo di T e lo insieriamo in mosse. *) mosse := High(mosse); FOR j:=1 TO DIM DO FOR k:=1 TO DIM DO mosse := min(mosse, T[j][k]); (* Seconda fase: dobbiamo provare ad fare incontrare il re con ogni cavaliere. *) FOR i:=1 TO ncav DO BEGIN (* Inizializziamo a oo la matrice di distanze "re in groppa a cavaliere". *) FOR j:=1 TO DIM DO FOR k:=1 TO DIM DO Drecav[j][k] := High(Drecav[j][k]); (* Ora scandiamo i possibili punti di partenza e di arrivo di un re in groppa al cavaliere i. Il costo per raggiungere un punto di partenza dato e` Dre[j][k] + Dcav[i][j][k]. Quindi per sapere il costo minimo in mosse per raggiungere una posizione dobbiamo minimizzare su tutti i possibili punti di incontro il numero di mosse necessario al re e al cavallo (separatamente) per raggiungere e il numero di mosse necessarie per raggiungere da (insieme). *) FOR j:=1 TO DIM DO FOR k:=1 TO DIM DO (* Questi cicli scandiscono il punto di partenza. *) BEGIN (* T ci dice in quante mosse il cavallo (con in groppa il re) riesce a raggiungere una qualunque posizione a partire da . *) distmin(T, j, k, mosse_cav); FOR p:=1 TO DIM DO FOR q:=1 TO DIM DO (* Qui scandiamo il punto di arrivo. *) Drecav[p][q] := min(Drecav[p][q], Dre[j][k] + Dcav[i][j][k] + T[p][q]); END; (* A questo punto Drecav[p][q] contiene il numero minimo di mosse necessarie al cavallo i e al re per raggiungere la posizione insieme. Sommando la matrice Drecav con tutte le Dcav (tranne quella di indice i) otteniamo una matrice che da` il numero globale di mosse necessarie per raggiungere le varie posizioni della scacchiera se il cavaliere i si prende in groppa il re.*) FOR j:=1 TO NCAV DO IF i <> j THEN FOR p:=1 TO DIM DO FOR q:=1 TO DIM DO Drecav[p][q] := Drecav[p][q] + Dcav[j][p][q]; (* Non ci resta che minimizzare mosse con il contenuto di Drecav. *) FOR p:=1 TO DIM DO FOR q:=1 TO DIM DO mosse := min(mosse, Drecav[p][q]); END; ASSIGN(F, ''); REWRITE(F); WRITELN(F, mosse); END.