Farmer John has recently built an enormous barn consisting of an N \times N grid of rooms (2 \leq N \leq 100), numbered from (1,1) up to (N,N). Being somewhat afraid of the dark, Bessie the cow wants to turn on the lights in as many rooms as possible.

Bessie starts in room (1,1), the only room that is initially lit. In some rooms, she will find light switches that she can use to toggle the lights in other rooms; for example there might be a switch in room (1,1) that toggles the lights in room (1,2). Bessie can only travel through lit rooms, and she can only move from a room (x,y) to its four adjacent neighbors (x-1,y), (x+1,y), (x,y-1) and (x,y+1) (or possibly fewer neighbors if this room is on the boundary of the grid).

Please determine the maximum number of rooms Bessie can illuminate.

Problem credits: Austin Bannister and Brian Dean

#3944 upload 4 done 2 how_to_reg 2

Switching on the Lights timer 2s memory 512MB

#3944

Switching on the Lights 2s 512MB