acm的一道问题，不知道为什么Time Limit Exceeded

Question

Description
Have you ever played Minesweeper? It's a cute little game which comes within a certain Operating System which name we can't really remember. Well, the goal of the game is to find where are all the mines within a MxN field. To help you, the game shows a number in a square which tells you how many mines there are adjacent to that square. For instance, supose the following 4x4 field with 2 mines (which are represented by an * character):

As you may have already noticed, each square may have at most 8 adjacent squares.
Input
The input will consist of an arbitrary number of fields. The first line of each field contains two integers n and m (0 < n,m <= 100) which stands for the number of lines and columns of the field respectively. The next n lines contains exactly m characters and represent the field. Each safe square is represented by an "." character (without the quotes) and each mine square is represented by an "*" character (also without the quotes). The first field line where n = m = 0 represents the end of input and should not be processed.Output
For each field, you must print the following message in a line alone:
Field #x:

Where x stands for the number of the field (starting from 1). The next n lines should contain the field with the "." characters replaced by the number of adjacent mines to that square. There must be an empty line between field outputs.
Sample Input
4 4
*...
....
.*..
....
3 5
**...
.....
.*...
0 0
Output
Field #1:
*100
2210
1*10
1110

Field #2:
**100
33200
1*100代码在http://bbs.bccn.net/viewthread.php?tid=418491&extra=page%3D1&frombbs=1

Answer 1

如果你TLE的话，那么这就一定是一道卡常数时间的题了。

题意很简单，从你代码中也可以看出，你对每一个点的周围8个均做了判断，那么这一块计算的最大复杂度就是100*100*8，其实只要建一个辅助数组f[101][101]，f[i][j]表示从左上角(0,0)到(i,j)的雷的总数量，那么f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + ( (i,j)是否为雷 ? 1:0 );

通过这个递推式子可以在O(nm)也就是最坏100*100的情况下求得f[i][j]的所有值，最后输出答案的时候若(i,j)不是雷，那么(i,j)上的答案就是f[i+1][j+1] - f[i+1][j-2] - f[i-2][j+1] + f[i-2][j-2]。

这样就不用对每个点的相邻8个点一一进行判断，时间上就可以快8倍。希望这种利用容斥优化的思想对你有所帮助。