O(MN) C# solution with DP.


  • 0
    S
    public class Solution {
    
    	const char EMPTY = '0';
    	const char WALL = 'W';
    	const char ENEMY = 'E';
    
        public int MaxKilledEnemies(char[,] grid) {
            
    	//TODO: ensure grid is not null
    	
    	int rows = grid.GetLength(0);
    	int cols = grid.GetLength(1);
    
    	Dictionary<int, int> rowLookup = new Dictionary<int, int>();
    	Dictionary<int, int> colLookup = new Dictionary<int, int>();
    	int[] colCounts = new int[cols];
    
    	int maxHits = 0, rowHits = 0, colHits = 0;
    
        char item;
        int rowCount;
    	for(int r = 0; r < rows; r++)
    	{
    	    rowCount = 0;
    		for (int c = 0; c < cols; c++)
    		{
    		    item = grid[r,c];
    			if(item == EMPTY)
    			{
    				if (rowLookup.ContainsKey(r * cols + c))
    				{
    					rowHits = rowLookup[r * cols + c];
    				}
    				else
    				{
    					rowHits = CountRowHits(r, c, rows, cols, rowCount, grid, rowLookup);
    				}
    
    				if (colLookup.ContainsKey(r * cols + c))
    				{
    					colHits = colLookup[r * cols + c];
    				}
    				else
    				{
    					colHits = CountColHits(r, c, rows, cols, colCounts[c], grid, colLookup);
    				}
    
    				maxHits = Math.Max(maxHits, rowHits + colHits);
    			}
    			else if (item == WALL)
    			{
    			    rowCount = 0;
    			    colCounts[c] = 0;
    			}
    			else if (item == ENEMY)
    			{
    			    rowCount++;
    			    colCounts[c]++;
    			}
    		}
    	}
    
    	return maxHits;
    	
        }
    
    	public int CountRowHits(int r, int c, int rows, int cols, int rowCount, char[,] grid, Dictionary<int, int> lookup)
    	{
    		List<int> discovered = new List<int>();
    		int count = rowCount;
    
            char item;
    		//Scan right
    		for(int i = c + 1; i < cols; i++)
    		{
    			item = grid[r, i];
    			if (item == WALL) 
    			{
    				break;
    			}
    			else if (item == ENEMY)
    			{
    				count++;
    			}
    			else if (item == EMPTY)
    			{
    				discovered.Add(r * cols + i);
    			}
    			
    		}
    
    		foreach(int e in discovered)
    		{
    			lookup[e] = count;
    		}
    
    		return count;
    		
    		
    	}
    
    	public int CountColHits(int r, int c, int rows, int cols, int colCount, char[,] grid, Dictionary<int, int> lookup)
    	{
    		List<int> discovered = new List<int>();
    		int count = colCount;
    
            char item;
    		//Scan down
    		for(int i = r + 1; i < rows; i++)
    		{
    			item = grid[i, c];
    			if (item == WALL) 
    			{
    				break;
    			}
    			else if (item == ENEMY)
    			{
    				count++;
    			}
    			else if (item == EMPTY)
    			{
    				discovered.Add(i * cols + c);
    			}
    			
    		}
    
    		foreach(int e in discovered)
    		{
    			lookup[e] = count;
    		}
    
    		return count;
    		
    		
    	}
    
    }
    
    

Log in to reply
 

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