# 算法细节系列（16）：深度优先搜索

## 329 Longest Increasing Path in a Matrix

Problem:

Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [ [9,9,4], [6,6,8], [2,1,1] ] Return 4 The longest increasing path is [1,2,6,9]

Example 2:

nums = [ [3,4,5], [3,2,6], [2,2,1] ] Return 4 The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

```public int longestIncreasingPath(int[][] matrix) {

row = matrix.length;
if (row == 0) return 0;
col = matrix[0].length;
if (col == 0) return 0;

max = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
count = 1;
dfs(matrix,i,j);
}
}
return max;
}

static int count = 1;
static int max = 0;
static int row,col;
static final int[][] direction = {{-1,0},{1,0},{0,-1},{0,1}};

private void dfs(int[][] matrix, int cx, int cy){
for (int i = 0; i < 4; i++){
int nx = cx + direction[i][0];
int ny = cy + direction[i][1];
max = Math.max(max, count);
if (nx >= 0 && nx < row && ny >=0 && ny < col && matrix[nx][ny] > matrix[cx][cy]){
count++;
dfs(matrix, nx, ny);
//注意状态还原
count--;
}
}
}```

```public int longestIncreasingPath(int[][] matrix) {

int row = matrix.length;
if (row == 0) return 0;
int col = matrix[0].length;
if (col == 0) return 0;

int[][] cache = new int[row][col];

int max = 1;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
int len = dfs(matrix, i, j, row, col, cache);
max = Math.max(len, max);
}
}
return max;
}

final static int[][] direction = {{-1,0},{1,0},{0,-1},{0,1}};

private int dfs(int[][] matrix, int i , int j, int row, int col, int[][] cache){
if (cache[i][j] != 0) return cache[i][j];
int max = 1;
for (int[] dir : direction){
int nx = i + dir[0], ny = j + dir[1];
if (nx < 0 || nx >= row || ny < 0 || ny >= col || matrix[nx][ny] <= matrix[i][j]) continue;
int len = 1 + dfs(matrix, nx, ny, row, col, cache);
max = Math.max(max, len);
}
return cache[i][j] = max;
}```

DFS带返回值的特点，天然的能够进行一些状态还原，所以不需要像第一版代码一样，在DFS后加入`count--`

## 488 Zuma Game

Problem:

Think about Zuma Game. You have a row of balls on the table, colored red(R), yellow(Y), blue(B), green(G), and white(W). You also have several balls in your hand. Each time, you may choose a ball in your hand, and insert it into the row (including the leftmost place and rightmost place). Then, if there is a group of 3 or more balls in the same color touching, remove these balls. Keep doing this until no more balls can be removed. Find the minimal balls you have to insert to remove all the balls on the table. If you cannot remove all the balls, output -1.

Examples:

Input: “WRRBBW”, “RB” Output: -1 Explanation: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW Input: “WWRRBBWW”, “WRBRW” Output: 2 Explanation: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty Input:”G”, “GGGGG” Output: 2 Explanation: G -> G[G] -> GG[G] -> empty Input: “RBYYBBRRB”, “YRBGB” Output: 3 Explanation: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty

Note:

• You may assume that the initial row of balls on the table won’t have any 3 or more consecutive balls with the same color.
• The number of balls on the table won’t exceed 20, and the string represents these balls is called “board” in the input.
• The number of balls in your hand won’t exceed 5, and the string represents these balls is called “hand” in the input.
• Both input strings will be non-empty and only contain characters ‘R’,’Y’,’B’,’G’,’W’.

```public int findMinStep(String board, String hand) {
int[] handCount = new int[32];
for (int i = 0; i < hand.length(); i++){
handCount[hand.charAt(i)-'A']++; //顺序无关
}
int min_step = helper(board + "#", handCount);
return min_step == 6 ? -1 : min_step;
}

private int helper(String board, int[] handCount){
String s = removeConsecutive(board);
if (s.equals("#")) return 0;
char[] cc = s.toCharArray();
int min_step = 6;
for (int i = 0, j = 0; j < s.length(); j++){
int step = 0;
if (cc[i] == cc[j]) continue;
// j - i = 1 or 2
int need = 3- (j - i);
if (need <= handCount[cc[i]-'A']){
step += need;
handCount[cc[i]-'A'] -= need;
min_step = Math.min(min_step,step + helper(s.substring(0, i) + s.substring(j), handCount));
handCount[cc[i]-'A'] += need;
}
i = j;
}
return min_step;
}

private String removeConsecutive(String board) {
char[] cc = board.toCharArray();
for (int i = 0, j = 0; j < cc.length; j++){
if (cc[i] == cc[j]) continue;
if (j - i >= 3) return removeConsecutive(board.substring(0, i) + board.substring(j));
else i = j;
}
return board;
}```

## 417 Pacific Atlantic Water Flow

Problem:

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges. Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower. Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

• The order of returned grid coordinates does not matter.
• Both m and n are less than 150.

Example:

Given the following 5x5 matrix: Pacific ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7) 1 4 5 * ~ (5) 1 1 2 4 * * * * * * Atlantic Return: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

```public List<int[]> pacificAtlantic(int[][] matrix) {
int row = matrix.length;
if (row == 0) return new ArrayList<int[]>();
int col = matrix[0].length;
if (col == 0) return new ArrayList<int[]>();

List<int[]> ans = new ArrayList<>();
boolean[][] a = new boolean[row][col];
boolean[][] p = new boolean[row][col];

for (int i = 0; i < row; i++){
dfs(matrix, i, 0, Integer.MIN_VALUE, a);
dfs(matrix, i, col-1, Integer.MIN_VALUE, p);
}

for (int j = 0; j < col; j++){
dfs(matrix, 0, j, Integer.MIN_VALUE, a);
dfs(matrix, row-1, j, Integer.MIN_VALUE, p);
}

for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (a[i][j] && p[i][j]){
}
}
}
return ans;
}

int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
private void dfs(int[][] matrix, int i, int j, int height, boolean[][] visited){
int row = matrix.length, col = matrix[0].length;
if (i < 0 || i >= row || j < 0 || j >= col || matrix[i][j] < height || visited[i][j]){
return;
}
visited[i][j] = true;
for (int[] d : dir){
dfs(matrix, i+d[0], j+d[1], matrix[i][j], visited);
}
}```

## 332 Reconstruct Itinerary

Problem:

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

• If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].
• All airports are represented by three capital letters (IATA code).
• You may assume all tickets form at least one valid itinerary.

Example 1:

tickets = [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] Return [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”].

Example 2:

tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]] Return [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]. Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]. But it is larger in lexical order.

```public List<String> findItinerary(String[][] tickets) {
Map<String, PriorityQueue<String>> targets = new HashMap<>();
for (String[] ticket : tickets)
visit("JFK",targets);
return route;
}

private void visit(String airport, Map<String, PriorityQueue<String>> targets) {
while (targets.containsKey(airport) && !targets.get(airport).isEmpty())
visit(targets.get(airport).poll(), targets);
}```

0 条评论

• ### 挑战程序竞赛系列（30）：3.4矩阵的幂

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（36）：3.3线段树和平方分割

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（32）：4.5 A*与IDA*

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### POJ 1985 Cow Marathon(树的直径)

Description After hearing about the epidemic of obesity in the USA, Farmer John...

• ### 「POJ - 2318」TOYS (叉乘)

有一个玩具盒，被n个隔板分开成左到u右n+1个区域，然后给每个玩具的坐标，求每个区域有几个玩具。

• ### Noip 2016 Day1 题解

老师让我们刷历年真题， 然后漫不经心的说了一句：“你们就先做做noip2016 day1 吧” 。。。。。。 我还能说什么，，，，，老师你这是明摆着伤害我们啊2...

• ### Python3 基础学习之数值进制转换

这个函数在上篇里表示强转，并没有输入n这个参数。当n不输入的时候默认是n=10。

• ### poj-------(2240)Arbitrage(最短路)

Arbitrage Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 156...

• ### Codeforces Round #186 (Div. 2)A、B、C、D、E

Ilya得到了一个礼物，可以在删掉银行账户最后和倒数第二位的数字（账户有可能是负的），也可以不做任何处理。

• ### 2019 CCPC 重现赛 1006 基环树

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...