acm的一道问题,不知道为什么Time Limit Exceeded
来源:学生作业帮 编辑:作业帮 分类:英语作业 时间:2024/10/06 08:12:44
acm的一道问题,不知道为什么Time Limit Exceeded
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
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
如果你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倍.希望这种利用容斥优化的思想对你有所帮助.
题意很简单,从你代码中也可以看出,你对每一个点的周围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倍.希望这种利用容斥优化的思想对你有所帮助.
ACM 的一道题提交总是Time Limit Exceeded,求救
Time Limit Exceeded和Output Limit Exceeded有什么不同,还是一样的?
hdoj1032 3n+1问题 time limit exceeded
一道acm题,Problem H:Groups (I)Time Limit:1000MS Memory Limit:65
杭电里面的Output Limit Exceeded
这是一道acm题目,不知道为什么我的答案总是不对
ACM的 “顺”序列 Time Limit:1000MS Memory Limit:32768K
Bandwidth Limit Exceeded
新手请教ACM水题Q - 数据的交换输出Time Limit:1000MS Memory Limit:32768KB 6
一道数学的ACM题.1514:x + 2y + 3z = nTime Limit:1000MS Memory Limit
user limit exceeded check your license的汉语意思是什么?
一个很简单的ACM题,这个提交后怎么会“Time Limit Exceed”?