机器人的运动范围

Posted on Edited on In Views: Waline: Symbols count in article: 187 Reading time ≈ 1 mins.

题解方法

  • 广度优先搜索
  • 深度优先搜索

广度优先搜索

经典 BFS

深度优先搜索

经典 DFS

核心代码

广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int movingCount(int m, int n, int k) {  
	this.k = k;  
	boolean[][] visited = new boolean[m][n];  
	int count = 0;  
	Queue<int[]> queue = new LinkedList<>();  
	queue.add(new int[]{0, 0});  
	while (!queue.isEmpty()) {  
		int[] cur = queue.poll();  
		int i = cur[0], j = cur[1];  
		if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || !isAccessed(i, j)) {  
			continue;  
		}  
		visited[i][j] = true;  
		count++;  
		queue.add(new int[]{i + 1, j});  
		queue.add(new int[]{i, j + 1});  
	}  
	return count;  
}

深度优先搜索

1
2
3
4
5
6
7
8
9
10
private void search(int i, int j) {  
	if (i < 0 || i >= visited.length || j < 0 || j >= visited[0].length || visited[i][j] || !isAccessed(i, j)) {  
		return;  
	}  
	  
	visited[i][j] = true;  
	count++;  
	search(i + 1, j);  
	search(i, j + 1);  
}

题目来源