110.字符串接龙
题目链接：https://kamacoder.com/problempage.php?pid=1183
文档讲解：https://programmercarl.com/kamacoder/0110.%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%8E%A5%E9%BE%99.html
思路
本题只需要求出最短路径的长度就可以了，不用找出具体路径。所以这道题要解决两个问题：
- 图中的线是如何连在一起的
- 起点和终点的最短路径长度
首先题目中并没有给出点与点之间的连线，而是要我们自己去连，条件是字符只能差一个。所以判断点与点之间的关系，需要判断是不是差一个字符，如果差一个字符，那就是有链接。
然后就是求起点和终点的最短路径长度，这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。
本题如果用深搜，会比较麻烦，要在到达终点的不同路径中选则一条最短路。 而广搜只要达到终点，一定是最短路。另外需要有一个注意点：
- 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环。
- 使用set来检查字符串是否出现在字符串集合里更快一些。
代码
import java.util.*;
class Main {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String beginStr = in.next();
String endStr = in.next();
Set<String> strList = new HashSet<>();
for (int i = 0; i < n; i++) strList.add(in.next());
// 记录strList中的字符串是否被访问过，并记录路径长度
HashMap<String, Integer> map = new HashMap<>();
Queue<String> queue = new LinkedList<>();
queue.offer(beginStr);
map.put(beginStr, 1);
while (!queue.isEmpty()) {
String word = queue.poll();
int pathLen = map.get(word);
for (int i = 0; i < word.length(); i++) {
char[] newWordCh = word.toCharArray();
for (char j = 'a'; j <= 'z'; j++) {
newWordCh[i] = j;
String newWord = new String(newWordCh);
if (newWord.equals(endStr)) {
System.out.println(pathLen + 1);
return;
}
if (strList.contains(newWord) && !map.containsKey(newWord)) { // 字典中存在且未被访问
queue.offer(newWord);
map.put(newWord, pathLen + 1);
}
}
}
}
System.out.println(0);
}
}
105.有向图的完全可达性
题目链接：https://kamacoder.com/problempage.php?pid=1177
文档讲解：https://programmercarl.com/kamacoder/0105.%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%AE%8C%E5…
思路
深搜三部曲：
1、确认递归函数，参数
需要知道当前我们拿到的key，以至于去下一个节点。同时还需要一个数组，用来记录我们都走过了哪些节点，这样好知道最后有没有把所有节点都遍历的，可以定义一个一维数组。
2、确认终止条件
遍历的时候，什么时候终止呢？这里有一个很重要的逻辑，就是在递归中，我们是处理当前访问的节点，还是处理下一个要访问的节点。如果是处理当前访问节点，则在递归开始时判断当前节点是否处理过，如果处理过就return。如果是处理下一个要访问的节点，需要判断下一个节点是否被访问过，如果被访问，则不继续dfs。
3、处理目前搜索节点出发的路径
visited数组来记录访问过的节点，该节点默认数组里元素都是false，把元素标记为true就是处理本节点了。
代码
import java.util.*;
class Main{
static int[][] grid;
static int n, k;
static boolean[] visited;
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
k = in.nextInt();
grid = new int[n + 1][n + 1];
visited = new boolean[n + 1];
for (int i = 0; i < k; i++) {
int tmp1 = in.nextInt(), tmp2 = in.nextInt();
grid[tmp1][tmp2] = 1;
}
visited[1] = true;
dfs(1);
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
System.out.println(-1);
return;
}
}
System.out.println(1);
}
public static void dfs(int i) {
// 处理下一个节点
for (int j = 1; j <= n; j++) {
if (!visited[j] && grid[i][j] == 1) {
visited[j] = true;
dfs(j);
}
}
}
}
106.岛屿的周长
题目链接：https://kamacoder.com/problempage.php?pid=1178
文档讲解：https://programmercarl.com/kamacoder/0106.%E5%B2%9B%E5%B1%BF%E7%9A%84%E5%91%A8%E9%95%BF.html
思路
- 解法一：用dfs或bfs，找到一块水，就等于一条边长；或者一条边出界，也算是一条边长。好吧，果然惯性思维了。
- 解法二：通过遍历二维数组，遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。如果该陆地上下左右的空格是有水域，则说明是一条边；如果该陆地上下左右的空格出界了，则说明是一条边。
- 解法三：岛屿数
result = 岛屿数量 * 4 - cover * 2;，找到陆地后，分别统计该陆地上边和左边是否相邻陆地。不统计右边和下边，防止重复。
代码
解法一：dfs法
import java.util.*;
class Main {
static int n, m, count = 0;
static int[][] grid;
static boolean[][] visitied;
static int[][] dir = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
grid = new int[n][m];
visitied = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = in.nextInt();
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visitied[i][j] && grid[i][j] == 1) {
visitied[i][j] = true;
dfs(i, j);
}
}
}
System.out.println(count);
}
public static void dfs(int x, int y) {
for (int i = 0; i < 4; i++) {
int nextX = x + dir[i][0], nextY = y + dir[i][1];
if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m) {
count++;
continue;
}
if (grid[nextX][nextY] == 0) count++;
if (!visitied[nextX][nextY] && grid[nextX][nextY] == 1) {
visitied[nextX][nextY] = true;
dfs(nextX, nextY);
}
}
}
}
解法二：遍历数组
import java.util.*;
class Main {
static int n, m, count = 0;
static int[][] grid;
static int[][] dir = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = in.nextInt();
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) {
for (int k = 0; k < 4; k++) {
int x = i + dir[k][0], y = j + dir[k][1];
if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) count++;
}
}
}
}
System.out.println(count);
}
}
解法三
import java.util.*;
class Main {
static int n, m;
static int[][] grid;
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = in.nextInt();
}
}
int sum = 0, cover = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) {
sum++;
if (i - 1 >= 0 && grid[i - 1][j] == 1) cover++;
if (j - 1 >= 0 && grid[i][j - 1] == 1) cover++;
}
}
}
System.out.println(sum * 4 - cover * 2);
}
}