Das Diagramm zeigt den Plan einer Stadt; die schwarzen Linien sind die Straßen.
Die grauen Punkte sind mögliche Standorte von Überwachungsbeamten. So ein
Beamter kann genau zwei Planquadrate weit sehen, horizontal oder vertikal. Er
kann nur die Straßen beobachten, auf denen er gerade steht. Bestimmen Sie die
Standorte, auf denen man Überwachungsbeamte aufstellen muss, um mit minimaler
Anzahl an Beamten alle Straßenstücke zu beobachten.
The black lines represent streets of a city. There are watchers on some of the
grey points. A watcher can only see two linear units away from where he stands.
He can’t see a point which is not on one of the streets he stands on. Locate
the fewest number of watchers possible onto some of the grey points in order to
watch all of the street lines.
Regeln