lets consider theatre to be a matrix of size n*m(n-rows,m-colums) and define adjacent seats to seat s(i,j) as s(i+1,j),s(i-1,j),s(i,j+1),s(i,j-1).Also some 'q' seats are blocked(may be chair is broken in theatre).what is the maximum number seats that u can select with given constraints?? n<=5; m<=1000; q<=m*n
my idea--i represented it as a graph and eliminated the broken seats,but for all connected componets i have find the maximum seats with this condition(but i do not know how?)
any ideas?
