C# DP sum left,right,up,down 4 directions, time O(mn), space O(mn)


  • 0
    Y
    public class point
    {
        public int left;
        public int right;
        public int up;
        public int down;
    }
    public class Solution {
        public int MaxKilledEnemies(char[,] grid) {
            int rows=grid.GetLength(0);
            int cols=grid.GetLength(1);
            if(rows==0||cols==0)
                return 0;
            point[,] leftTopDP=new point[rows,cols];
            
            for(int i=0;i<rows;i++)
            {
                for(int j=0;j<cols;j++)
                {
                    leftTopDP[i,j]=new point();
                    int left = (j>0?leftTopDP[i,j-1].left:0);
                    int up = (i>0?leftTopDP[i-1,j].up:0);
                    if(grid[i,j]=='E')
                        {leftTopDP[i,j].left=left + 1;
                        leftTopDP[i,j].up=up + 1;}
                    else if(grid[i,j]=='0')
                        {leftTopDP[i,j].left=left;
                        leftTopDP[i,j].up=up;}
                    else
                        {leftTopDP[i,j].left=0;
                        leftTopDP[i,j].up=0;}
                }
            }
            for(int i=rows-1;i>=0;i--)
            {
                for(int j=cols-1;j>=0;j--)
                {
                    int right=(j<cols-1?leftTopDP[i,j+1].right:0);
                    int bot=(i<rows-1?leftTopDP[i+1,j].down: 0);
                    if(grid[i,j]=='E')
                        {leftTopDP[i,j].right=right + 1;
                        leftTopDP[i,j].down=bot + 1;}
                    else if(grid[i,j]=='0')
                        {leftTopDP[i,j].right=right;
                        leftTopDP[i,j].down=bot;}
                    else
                        {leftTopDP[i,j].right=0;
                        leftTopDP[i,j].down=0;}
                }
            }
            int max=0;
            for(int i=0;i<rows;i++)
            {
                for(int j=0;j<cols;j++)
                {
                    if(grid[i,j]=='0')
                        max=Math.Max(max,leftTopDP[i,j].left+leftTopDP[i,j].right+leftTopDP[i,j].up+leftTopDP[i,j].down);
                }
            }
            return max;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.