描述

给定一个二维矩阵, 每一个格子可能是一堵墙 W,或者 一个敌人 E 或者空 0 (数字 ‘0’), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固，所以墙不会被摧毁.

你只能在空的地方放置炸弹.

样例1

输入:
grid =[
“0E00”,
“E0WE”,
“0E00”
]
输出: 3
解释:
把炸弹放在 (1,1) 能杀3个敌人
样例2

输入:
grid =[
“0E00”,
“EEWE”,
“0E00”
]
输出: 2
解释:
P把炸弹放在 (0,0) 或 (0,3) 或 (2,0) 或 (2,3) 能杀2个敌人

思路1（超时）：遍历grid的每个0的位置，然后上下左右扫描，遇到敌人+1，遇到边界或墙停止，然后与max比较取大者
方法暴力，结果不出意料地超时，因为每个0点都上下左右扫描，最坏情况2n^3复杂度
思路2（通过，速度超过90%+）：
重新声明一个矩阵g，每个点存两个数，用pair<int,int>，一个x方向击杀的敌人，一个y方向击杀的敌人，两个加起来就是总击杀
第一次扫描
扫描每行，并int r =0遇到一个0把这个索引记录，遇到一个敌人把r++，遇到墙或者边界就把记录的索引的g矩阵第一个值赋r，
然后把记录和r清零
该值就是当前位置在这一行能击杀的敌人数
然后扫描到结尾，得到这个图的每个位置能击杀的x方向的敌人

第二次扫描
扫描每列，方法同上，得到这个图每个位置能击杀的y方向敌人

第三次扫描
将g的每个节点的first值和second值相加，然后取大者，返回

int maxKilledEnemies(vector<vector<char>> &grid) {
		// write your code here
		if (!grid.size())
			return 0;
		int row = grid.size();
		int col = grid[0].size();
		int max = 0;
		vector<vector<pair<int, int>>> g(row, vector<pair<int, int>>(col, pair<int, int>(-1, -1)));
		vector<int> set;
		int k = 0;
		for (int i = 0; i < row; ++i)
		{
			for (int j = 0; j < col; ++j)
			{
				if (grid[i][j] == '0')
				{
					set.push_back(j);
				}
				else if (grid[i][j] == 'E')
				{
					++k;
				}
				
				if(grid[i][j]=='W'||j==col-1)
				{
					for (int &a : set)
					{
						g[i][a].first = k;
					}
					k = 0;
					set.clear();
				}
			}
		}

		for (int i = 0; i < col; ++i)
		{
			for (int j = 0; j < row; ++j)
			{
				if (grid[j][i] == '0')
				{
					set.push_back(j);
				}
				else if (grid[j][i] == 'E')
				{
					++k;
				}

				if (grid[j][i] == 'W' || j == row - 1)
				{
					for (int &a : set)
					{
						g[a][i].second = k;
					}
					k = 0;
					set.clear();
				}
			}
		}

		for (int i = 0; i < row; ++i)
		{
			for (int j = 0; j < col; ++j)
			{
				if (grid[i][j] != '0')
					continue;
				int sum = g[i][j].first + g[i][j].second;
				if (sum > max)
					max = sum;
			}
		}

		return max;
	}