Problema politistilor

[•caliucii]

Într-un oraş sunt n intersectii. Anumite intersectii sunt legate prin strazi. Sa se dispuna în intersectii un nunar minim de politisti astfel încât toate străzile sa fie supravegheate.

Am inţeles că e vorba de o matrice bidemensională  :
1 1 1 1 1 1 1 1 1 1 1 1        unde 1- este perete ( calădiri) 0- sunt strazi.
1 0 0 0 0 1 0 0 0 1 0 1        am nevoie sa plasezi politisti. dar nu am dedus algoritmul. am nevoie de idei.
1 1 1 1 0 1 1 0 1 1 0 1
1 1 1 1 0 0 0 0 0 0 0 1          accept ajutor in fraze sau in c (dar nu in c++). multumiri anticipate.
1 0 0 0 0 0 1 1 0 1 0 1
1 1 1 1 1 0 0 1 0 1 1 1     
1 1 0 0 0 0 1 1 0 0 0 1
1 1 0 1 1 0 0 1 1 0 1 1
1 0 0 0 1 0 0 0 0 0 0 1
1 1 1 1 1 0 1 1 0 1 1 1
1 0 0 0 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1

[•wefgef]

http://en.wikipedia.org/wiki/Vertex_cover

[•caliucii]

multumesc petru indrumare !  o sa citesc apoi revin daca ceva nui clar.