10521 - 蜗牛的旅行

萨丽·斯内尔（Sally Snail，蜗牛）喜欢在 N x N 的棋盘上闲逛（1 < n < 120）。她总是从棋盘的左上角出发。棋盘上有空的格子（用“.”来表示）和 B 个路障（用“#”来表示）。下面是这种表示法的示例棋盘：

      A B C D E F G H
    1 S . . . . . # .
    2 . . . . # . . .
    3 . . . . . . . .
    4 . . . . . . . .
    5 . . . . . # . .
    6 # . . . . . . .
    7 . . . . . . . .
    8 . . . . . . . .

萨丽总是垂直（向上或者向下）或水平（向左或者向右）地走。她可以从出发地（总是记作 A1 ）向下或者向右走。 一旦萨丽选定了一个方向，她就会一直走下去。如果她遇到棋盘边缘或者路障，她就停下来，并且转过 90 度。她不可能离开棋盘，或者走进路障当中。并且，萨丽从不跨过她已经经过的格子。当她再也不能走的时候，她就停止散步。

这里是上面的棋盘上的一次散步路线图示：

     A B C D E F G H
    1 S---------+ # .
    2 . . . . # | . .
    3 . . . . . | . .
    4 . . . . . +---+
    5 . . . . . # . |
    6 # . . . . . . |
    7 +-----------+ |
    8 +-------------+

萨丽向右走，再向下，向右，向下，然后向左，再向上，最后向右走。这时她遇到了一个她已经走过的格子，她就停下来了。但是，如果她在 F5 格遇到路障后选择另外一条路——向我们看来是左边的方向转弯，情况就不一样了。

你的任务是计算并输出，如果萨丽聪明地选择她的路线的话，她所能够经过的最多格子数。

输入的第一行包括 N ——棋盘的大小，和 B ——路障的数量（1 <= B <= 200）。接下来的 B 行包含着路障的位置信息。下面的样例输入对应着上面的示例棋盘。下面的输出文件表示问题的解答。注意，当 N 〉26 时，输入文件就不能表示 Z 列以后的路障了。

输出文件应该只由一行组成，即萨丽能够经过的最多格子数。

Snail Trails All Ireland Contest Sally Snail likes to stroll on a N x N square grid (1 <n < 120). She always starts in the upper left corner of the grid. The grid has empty squares (denoted below by .') and a number (B) of barriers (denoted below by #'). Here is a depiction of a grid including a demonstration of the grid labelling algorithm:

      A B C D E F G H
    1 S . . . . . # .
    2 . . . . # . . .
    3 . . . . . . . .
    4 . . . . . . . .
    5 . . . . . # . .
    6 # . . . . . . .
    7 . . . . . . . .
    8 . . . . . . . .

Sally travels vertically (up or down) or horizontally (left or right). Sally can travel either down or right from her starting location, which is always A1. Sally travels as long as she can in her chosen direction. She stops and turns 90 degrees whenever she encounters the edge of the board or one of the barriers. She can not leave the grid or enter a space with a barrier. Additionally, Sally can not re-cross any square she has already traversed. She stops her traversal altogether any time she can no longer make a move.

Here is one sample traversal on the sample grid above:

      A B C D E F G H
    1 S---------+ # .
    2 . . . . # | . .
    3 . . . . . | . .
    4 . . . . . +---+
    5 . . . . . # . |
    6 # . . . . . . |
    7 +-----------+ |
    8 +-------------+

Sally traversed right, down, right, down, left, up, and right. She could not continue since she encountered a square already visited. Things might have gone differently if she had chosen to turn back toward our left when she encountered the barrier at F5.

Your task is to determine and print the largest possible number of squares that Sally can visit if she chooses her turns wisely. Be sure to count square A1 as one of the visited squares.

PROGRAM NAME: snail INPUT FORMAT The first line of the input has N, the dimension of the square, and B, the number of barriers (1 <= B <= 200). The subsequent B lines contain the locations of the barriers. The sample input file below describes the sample grid above. The sample output file below is supposed to describe the traversal shown above. Note that when N > 26 then the input file can not specify barriers to the right of column Z.

SAMPLE INPUT (file snail.in) 8 4 E2 A6 G1 F5

OUTPUT FORMAT The output file should consist of exactly one line, the largest possible number of squares that Sally can visit.

SAMPLE OUTPUT (file snail.out) 33

Using this traversal:

      A B C D E F G H
    1 S . . . . . # .
    2 | . . . # . . .
    3 | . . . +-----+
    4 | . . . | . . |
    5 +-------+ # . |
    6 # . . . . . . |
    7 +------------ |
    8 +-------------+