algorithm - Visiting every cell in grid in the minimum time with these rules? -

a specimen placed in n x m size grid divided 1 x 1 cells.

it expands according following rules.

if @ time t, specimen occupies (x ,y), @ time t+1 can expand @ 2 cells out of (x+1,y), (x-1,y), (x,y+1), (x,y-1).

for example if @ t = 0 sec if specimen occupies (4, 5), @ time t = 1 sec, state of grid can of following

1. specimen @ (4,5), (5,5) , (3,5).  2. specimen @ (4,5), (5,5) , (4,6).  3. specimen @ (4,5), (5,5) , (4,4).  4. specimen @ (4,5), (3,5) , (4,6).  5. specimen @ (4,5), (3,5) , (4,4).  6. specimen @ (4,5), (4,6) , (4,4). 

note- @ t= 2 sec, can expand points specimen occupied @ t= 1

i plan greedy strategy,with breadth first search ,trying mark @ least 2 nodes in each step,after no 2 nodes can marked in single step ,i add remaining. approach give optimal result?

if not how can solved?

consider farthest corner of field specimen. example, if specimen in corner (1,1) farthest corner (n,m).

let's distance corner dx along x axis , dy along y axis. important insight is, no matter strategy chose, need @ least dx+dy steps colonize farthest corner. easy establish if 1 sees, after t steps no cell can colonized specimen further away t in manhattan distance.

now, if give strategy colonize whole field in dx+dy steps, optimal strategy, because strategy not have colonized farthest corner after dx+dy-1 step.

my strategy looks follows:

1. phase: dx steps grow in both x direction (as long both direction possible otherwise in direction of farthest corner). after phase whole row of field colonized (because our chosen farthest).

2. phase: dy steps grow in both y direction: after first step of phase there 3 full colonized rows, after second step - 5, , on until dy whole field colonized, due fact (the same above), chosen corner farthest.

so minimum time needed dx+dy.