Number of Islands II

305. Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array: [1, 1, 2, 3]

///////////////////////////////////////////////////////////////////////////////////
using a map to keep current islands:

unordered_map<int, vector<pair>> m;


for each coming island, check the four sides of the island,
and see it's connected to which existing island
 
           0
   0    new     0
      island 3

if all sides are 0, push back the new island into m;

otherwise, merge the current islands in the m.

repeat...............

LeetCode 425. Word Squares

Given a set of words (without duplicates), find all word squares you can build from them.

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.

b a l l
a r e a
l e a d
l a d y

Note:

1. There are at least 1 and at most 1000 words.
2. All words will have the exact same length.
3. Word length is at least 1 and at most 5.
4. Each word contains only lowercase English alphabet a-z.

Example 1:

Input:
["area","lead","wall","lady","ball"]

Output:
[
  [ "wall",
    "area",
    "lead",
    "lady"
  ],
  [ "ball",
    "area",
    "lead",
    "lady"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

/////////////////////////////////////////////////////////////////////////////

for (auto word:s)
    vector<vector<string>> res;
    vector<string> tmp;
    tmp.push_back(word);
    for(int i=1;i<word.size();i++)tmp.push_back(word[i]);
    int col=1;
    bt(&s, &res, &tmp, col){
         if(col==word.size())res.push_back(tmp);
         else{
               string subs=tmp[col];
               for(auto w:s){
                    if(word.substr(0, subs.size())==subs){
                         ..update tmp
                         bt(s, res, tmp, col+1);
                         ..de-update tmp
                    }
               }
        }
  }
};

361. Bomb Enemy

Given a 2D grid, each cell is either a wall 'Y', an enemy 'X' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note that you can only put the bomb at an empty cell.

Example:

For the given grid

0 w 0 0
e 0 e w
0 w 0 e

return 3. (Placing a bomb at (1,1) kills 3 enemies)

using DP:

DP with the same size of matrix mat;

each element is a pair (row, col), row means the sum of enimy in current row based on current position, col means the sum of enimy of column;

fill the DP one by one from left to right, when meet 'e', copy related value; meet 0, using DP or process; meet wall pass.

For the given mat

0 w 0 0
e 0 e w
0 w 0 e

build dp, with '-1' mean not applicable

(-1,-1) (-1,-1) (-1,-1) (-1,-1) 
(-1,-1) (-1,-1) (-1,-1) (-1,-1) 
(-1,-1) (-1,-1) (-1,-1) (-1,-1)

calculation: 

(0,0) (-1,-1) (0, 1) (0, 0) ........