Algorithm to enclose a 2D-gridbased-room efficient
This is a graph cut problem.

Build a graph with one vertex per square.  Add an edge between each pair of adjacent vertices (i.e., where you can go from one to the other in a single step).  Add an extra "source" vertex $s$, and an edge from $s$ to each starting point (yellow/green block).  Add an extra "sink" vertex $t$, and an edge from each exit to $t$.

Now your mission is to find a minimum vertex cut that separates $s$ from $t$, i.e., a subset $S$ of vertices such that every path from $s$ to $t$ traverses at least one vertex of $S$.  There are standard algorithms for the minimum vertex cut problem, which you can find by searching the literature.

See also https://en.wikipedia.org/wiki/Vertex_separator and https://cstheory.stackexchange.com/q/2877/5038 and https://cstheory.stackexchange.com/q/29464/5038.

You'll need to add the extra constraint that the subset $S$ cannot include $s$ nor $t$, but I expect it should be easy to incorporate this constraint into standard algorithms for vertex cut.