The legendary mercenary Solid Matt gets a classic mission: infiltrate a military base.
The military base can be seen as an N * N grid. Matt's target is in one of the grids and Matt is now in another grid.
In normal case, Matt can move from a grid to one of the four neighbor grids in a second. But this mission is not easy.
Around the military base there are fences, Matt can't get out of the base.
There are some grids filled with obstacles and Matt can't move into these grids.
There are also some surveillance cameras in the grids. Every camera is facing one of the four direction at first, but for every second, they will rotate 90 degree clockwisely. Every camera's sight range is 2, which means that if Matt is in the same grid as the camera, or in the grid that the camera is facing, he will be seen immediately and the mission will fail.
Matt has a special equipment to sneak: a cardbox. Matt can hide himself in the card box and move without being noticed. But In this situation, Matt will have to use 3 seconds to move 1 grid. Matt can also just hide in the cardbox without moving. The time to hide and the time to get out of the cardbox can be ignored.
Matt can't take the risk of being noticed, so he can't move without cardbox into a grid which is now insight of cameras or from a grid which is now insight of cameras. What's more, Matt may be in the cardbox at the beginning.
As a live legend, Matt wants to complete the mission in the shortest time.