Topic运行时限：2sec内存限制：1024MB有一个H行W列的网格区域。在这个网格区域中，障碍物被放置在一些网格中。小明会在这个格子区域选择一个没有障碍物的小格子，在小格子里放一盏灯。从放灯的小格子里，会有上、下、左、右四个方向射出的光束。这些光束会被其他网格中的障碍物阻挡，也会被网格区域的边缘阻挡。光线可以穿过放置灯光的小格子，但光线不能穿过放置障碍物的小格子。小明需要选择放灯的小格子的位置，让光束通过尽可能多的小格子。有H个长度为W的字符串，字符串表示为Si(1<=i<=H)。如果Si的第j个字符（1<=j<=W）为'#'，则格子区域从上到下第i行，从左到右第j列有障碍物。如果Si的第j个字符（1<=j<=W）为'.'，则网格区从上到下第i行，从左到右第j列没有障碍物。找出光束可以照亮的最大网格数。要求1<=H<=20001<=W<=2000Si是由'#'和'.'组成的长度为W的字符串Si(1<=i<=H)并且至少有一个'.'inputinput使用以下标准从命令行输入HWS1..SH输出。最多可以点亮多少个格子？例1输入46#..#.......#....#.#.#...例1从上到下第二行输出8小明，第二列放灯从左到右。如果灯在从上到下第二行，从左到右1到5列的格子就是从左到右第二列，从上到下1到4行，一共8个格子，所有的可以被照亮示例2输入88..#...#.....#...##........###..#...#..#.##....#.#...#...###.#..#例2输出13条解题思路理解题目1首先有一个网格板，相当于围棋棋盘。2.围棋棋盘上有几个格子有障碍物。3.只有一盏灯。图1解题思路遍历到这个格子的时候遍历每一个格子，求每盏灯放在这个格子上能照亮的范围有多大如何求遍历到的时候灯所覆盖的范围每个格子1个。我们实际上可以观察到，每个格子，光束从四个方向点亮。给定四个变量L、R、U、D，那么对于每个格子，将格子左边（包括格子本身）有多少个格子可以被照亮的值赋给变量L，有多少个格子可以被照亮右边的格子（包括格子本身）把格子上面（包括格子本身）能被照亮多少个格子的值赋值给变量R。把格子下面能被照亮多少个格子的值赋值（包括网格本身??）给变量U赋值给变量D如图1L=2U=2R=4D=3L+U+R+D=2+2+4+3=11应该是L,U,R,D都包含了网格本身，所以网格本身重算了4次，重算3次是多余的。最后的结果是11-3=8，那么最后的公式result=L+U+R+D-3怎么求L,U,R,D这时候如果分别遍历行和列，那么时间这里可能还不够用图2的叠加计算方式，可以感觉到L的值是左边格子中L的值+1，则Li=Li-1+1。同理，Ri=Ri+1+1Ui=Ui-1+1Di=Di+1+1特例1.当格子是障碍物时，L,R,U,D的值都为0，因为障碍物灯找不到2.上边时，U=1，因为上面没有格子，光束只能通过自己3.右边时，R=1，因为右边没有格子，光束只能穿过自己4.左边时，L=1，因为左边没有格子现在，光束只能穿过自己4.下边时，D=1，因为左边没有下面的网格，光束只能通过自己的代码#python不能满足时间要求#提交withpypy3defcalculate(h,w,arr):L=[[0]*wforiinrange(h)]U=[[0]*wforiinrange(h)]D=[[0]*wforiinrange(h)]R=[[0]*wforiinrange(h)]forihinrange(h):foriwinrange(w):ifih==0:U[ih][iw]=1如果iw==0:L[ih][iw]=1如果arr[ih][iw]==1:L[ih][iw]=0U[ih][iw]=0否则：如果iw>0：L[ih][iw]=L[ih][iw-1]+1如果ih>0：U[ih][iw]=U[ih-1][iw]+1rih=h-1-ihriw=w-1-iw如果rih==h-1:D[rih][riw]=1如果riw==w-1:R[rih][riw]=1如果arr[rih][riw]==1:D[rih][riw]=0R[rih][riw]=0否则:如果riw
