代码随想录算法训练营第四十六天 | 110. 字符串接龙 105.有向图的完全联通 106. 岛屿的周长
视频和文字的图 不是广搜过程的图，别看。
| 写法 | 类型 |
|---|---|
'a' | rune (int32) |
"a" | string |
byte('a') | byte (uint8) |
s[i] | byte |
for _, r := range s | rune |
package main import ( "bufio" "fmt" "os" ) func main() { in := bufio.NewReader(os.Stdin) var n int fmt.Fscan(in, &n) var beginStr, endStr string fmt.Fscan(in, &beginStr, &endStr) strSet := make(map[string]struct{}, n) for i := 0; i < n; i++ { var s string fmt.Fscan(in, &s) strSet[s] = struct{}{} } visitMap := make(map[string]int) q := make([]string, 0) q = append(q, beginStr) visitMap[beginStr] = 1 for len(q) != 0 { str := q[0] q = q[1:] for idx, val := range str { bs := []byte(str) for b := 'a'; b <= 'z'; b++ { if val == b { continue } bs[idx] = byte(b) newStr := string(bs) if newStr == endStr { fmt.Println(visitMap[str] + 1) return } if _, ok := strSet[newStr]; ok && visitMap[newStr] == 0 { visitMap[newStr] = visitMap[str] + 1 q = append(q, newStr) } } } } fmt.Println(0) }注意最后检查是否存在没访问过的结点时，要跳过visited[0]
package main import ( "bufio" "fmt" "os" ) func main() { in := bufio.NewReader(os.Stdin) var n, k int fmt.Fscan(in, &n, &k) gragh := make([][]int, n+1) visited := make([]bool, n+1) for i := range gragh { gragh[i] = make([]int, 0) } for i := 0; i < k; i++ { var s, t int fmt.Fscan(in, &s, &t) gragh[s] = append(gragh[s], t) } visited[1] = true dfs(gragh, visited, 1) for i := 1; i < len(visited); i++ { if !visited[i] { fmt.Println(-1) return } } fmt.Println(1) } func dfs(gragh [][]int, visited []bool, cur int) { for _, next := range gragh[cur] { if !visited[next] { visited[next] = true dfs(gragh, visited, next) } } }周长是边，不是格子。
package main import ( "bufio" "fmt" "os" ) var dir = [4][2]int{{0, 1}, {1, 0}, {-1, 0}, {0, -1}} func main() { in := bufio.NewReader(os.Stdin) var n, m int fmt.Fscan(in, &n, &m) grid := make([][]int, n) for i := range grid { grid[i] = make([]int, m) for j := range grid[i] { fmt.Fscan(in, &grid[i][j]) } } res := 0 for i := range grid { for j := range grid[i] { if grid[i][j] == 1 { for k := 0; k < 4; k++ { nextI := i + dir[k][0] nextJ := j + dir[k][1] if nextI < 0 || nextI >= len(grid) || nextJ < 0 || nextJ >= len(grid[0]) || grid[nextI][nextJ] == 0 { res++ } } } } } fmt.Println(res) }