Accensione delle luci#11157
Il contadino John ha recentemente costruito un enorme fienile composto da una griglia di stanze di dimensione n \times n, numerate da a . Poiché la mucca Bessie ha un po' paura del buio, vuole accendere la luce nel maggior numero possibile di stanze.
Bessie inizia nella stanza , che è l'unica stanza in cui la luce è inizialmente accesa. In alcune stanze troverà degli interruttori, grazie ai quali potrà accendere la luce in altre stanze. Ad esempio, nella stanza potrebbe trovarsi un interruttore che accende la luce nella stanza . Bessie può spostarsi solo tra le stanze in cui la luce è accesa, e dalla stanza può spostarsi solo in una delle quattro stanze adiacenti: (x - 1, y), (x + 1, y), (x, y - 1) oppure (x, y + 1) (o in un numero minore di stanze adiacenti, se la stanza si trova sul bordo della griglia).
Determinare il numero massimo di stanze in cui Bessie potrà accendere la luce.
La prima riga contiene due numeri interi e m~(2 \le n \le 100, 1 \le m \le 20000).
Ognuna delle successive righe descrive un interruttore e contiene quattro numeri interi x, y, a e . L'interruttore situato nella stanza può essere utilizzato per accendere la luce nella stanza . In una stessa stanza possono trovarsi più interruttori, e più interruttori possono accendere la luce nella stessa stanza.
Stampare un singolo numero intero — il numero massimo di stanze in cui Bessie potrà accendere la luce.
In questo esempio, Bessie può utilizzare l'interruttore nella stanza per accendere la luce nelle stanze e . Successivamente può spostarsi nella stanza e accendere la luce nella stanza , dalla quale potrà accendere la luce nella stanza . L'interruttore nella stanza non è raggiungibile, poiché si trova in una stanza con la luce spenta. Pertanto, Bessie potrà accendere la luce al massimo in stanze.
Esempio 1