0%

• 130 Surrounded Regions

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

• 将start入队列
• 每次取出队首（一共取当前层的长度），对队首每个字母分别进行变换（a~z)，判断其是否在字典中，如果存在，加入队列。
• 每一层结束后，将dis+1

• 和单向的不同在于，如果取出队首进行变化，变化的某一个字符串t在另一个方向的bfs中(如从start开始遍历的，而end已经遍历过t）说明有start->end的路径，将步数和累加即可。

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]

Return

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

• 标记使用过的单词应该这一层都遍历过才能标记，否则会出现答案不全。

### 130 Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

After running your function, the board should be:

C++

Python