Closed Lattice Curve

Define the degree of an intersection to be the number of streets leading out of the intersection. So the 4 intersections at the corners have degree 2, the $4\times12=48$ intersections at the edges have degree 3, and the remaining $12^2=144$ intersections in the middle have degree 4.

We will count the number of times Godzilla enters an intersection. This number is clearly equal to the number of blocks that he destroys. He can enter a degree 2 intersection at most once, and a degree 4 intersection at most twice. Also, if he enters and exits a degree 3 intersection he can no longer enter the same intersection again, because then he would have no way out. So he can only enter a degree 3 intersection at most once as well.

(The above argument also works for the intersection that Godzilla starts at, because he has to exit the intersection at the start and enter at the end.)

So the maximum number of blocks he can destroy is $144\times2+48+4=340$ .

To show that Godzilla can indeed destroy that many blocks, let us colour the blocks. Along each of the 4 edges, colour the blocks black and white alternately, starting with black. Colour the rest of the blocks black. Now there are $4\times6=24$ white blocks, and $2\times13\times14-24=340$ black blocks.

We want to show that Godzilla can destroy all the black blocks, so let us ignore the white blocks from now on. Then every intersection along the edges are degree 2, and the rest of the intersections are degree 4. Since the degree of every intersection is even, there exists an Eulerian circuit (i.e. a closed path that passes through all blocks) by a well-known theorem of Euler.

Hence Godzilla can destroy a maximum of $340$ blocks, which was what we wanted.

Redefine blocks as edges, and intersections as vertices. We now have a 14 by 14 square graph.

Observe that there are exactly 4*(14-2) = 48 vertices with degree 3. Note that any path Godzilla takes must pass through any vertex an even number of times (since the edges he passes through define a cycle). Thus he passes through these 48 vertices at most twice.

Define the 'score' of a vertex as the number of edges the vertex is on, that Godzilla passes through. Since 48 vertices are degree 3 and thus have a maximum score of 2, the maximum score is 2 (4) + 2 (48) + 4*(144) = 680.

Observe that for any path, the number of edges is equal to half the score. Thus the maximum number of edges is 340. We now simply need to construct such a path.

Taking the original graph, we colour the 169 squares (bordered by 4 edges of the graph) in a checkerboard fashion, with the 4 corner squares being black. Remove the edges on the border of this checkerboard that border a white square. This leaves us precisely 340 edges (we had 364 edges, and removed 6 from each side of the checkerboard, leaving 340). Furthermore, the resulting graph leaves every vertex with an even degree, and the graph is connected. Thus by Euler's theorem, an Eulerian path for this graph exists, which is a maximal path for Godzilla.

There are 14 x 13=182 vertical blocks and 14 x 13=182 horizontal blocks for a total of 364 blocks. An intersection with 2 or 4 blocks can be fully traversed by entering and exiting 1 or 2 times respectively. The intersections with 3 blocks, the ones on the border of the city (excluding the corners), pose a problem. Consider the top border with the blocks labelled from 1-13. Imagine "snipping" all the even blocks. Now each intersection on the border has 2 blocks and can be fully traversed. There are 4 x 6=24 "snipped" blocks. 364-24=340, and we are done.

Start from 2 2 squares grid, then 3 3,4 4,.. i found out that we cant fully destroy all blocks on the edges. With the most number of blocks that Godzilla could have destroyed if he ends his rampage at the same intersection that he started on, i figured out the missing block is 4 times floor of (n-1) divided by two, so with 14 14 streets we have 13 13 square grids, the number of blocks is 2 13 14=364 the missing blocks are 4 6=24 then the most number of blocks that Godzilla could have destroyed if he ends his rampage at the same intersection that he started on is 364-24=340

For Godzilla to end up back where he started, the number of times he leaves any intersection must equal the number of times he enters that intersection. Thus, for any intersection, the number of destroyed blocks around that intersection must be even. The $(12) \times (12)$ interior intersection have 4 blocks going in/out of them, so Godzilla passes through each of them at most twice. The boundary intersection have either 2 (for corners) or 3 blocks incident, so Godzilla passes through each of them at most once. Since we can think of the Godzilla's path as a list of intersections, we see that the list contains at most $2 \times 12^2 + 14^2 - 12^2 = 340$ intersections visited after leaving the starting position. The number of intersection points in the list is the same as the number of destroyed blocks, so $340$ is an upper bound on the number of destroyed blocks.

We claim that we can obtain the upper bound. Consider the four streets around the perimeter of the grid. If we delete the $2nd, 4th, \ldots$ blocks from each of these streets, then this leaves a set of blocks $\mathcal{B}$ such that each intersection is incident to an even number of blocks, every pair of intersections remains connected by blocks in $\mathcal{B}$ , and the number of blocks in $\mathcal{B}$ is equal to the upper bound.

From graph theory, we know that every intersection being incident with an even number of blocks is necessary and sufficient for finding a walk that visits each block exactly once and ends where it started (this is known as an Eulerian cycle). Thus $340$ is the final answer.