Water Flow Simulation
Siumlate water flow using two visited matriecs for tracking.
Depth-First Search Implementation
package main
import "fmt"
var dirs = [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func main() {
var rows, cols int
fmt.Scanln(&rows, &cols)
grid := make([][]int, rows)
vis1 := make([][]bool, rows)
vis2 := make([][]bool, rows)
for i := range grid {
grid[i] = make([]int, cols)
vis1[i] = make([]bool, cols)
vis2[i] = make([]bool, cols)
for j := range grid[i] {
fmt.Scan(&grid[i][j])
}
}
for i := 0; i < rows; i++ {
flood(i, 0, grid, vis1)
flood(i, cols-1, grid, vis2)
}
for j := 0; j < cols; j++ {
flood(0, j, grid, vis1)
flood(rows-1, j, grid, vis2)
}
for i := range grid {
for j := range grid[i] {
if vis1[i][j] && vis2[i][j] {
fmt.Printf("%d %d\n", i, j)
}
}
}
}
func flood(x, y int, grid [][]int, vis [][]bool) {
if vis[x][y] {
return
}
vis[x][y] = true
for _, d := range dirs {
nx, ny := x+d[0], y+d[1]
if nx >= 0 && nx < len(grid) && ny >= 0 && ny < len(grid[0]) {
if grid[nx][ny] >= grid[x][y] && !vis[nx][ny] {
flood(nx, ny, grid, vis)
}
}
}
}
Breadth-First Search Implementation
package main
import "fmt"
var dirs = [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
type point struct{ x, y int }
func main() {
var rows, cols int
fmt.Scanln(&rows, &cols)
grid := make([][]int, rows)
vis1 := make([][]bool, rows)
vis2 := make([][]bool, rows)
for i := range grid {
grid[i] = make([]int, cols)
vis1[i] = make([]bool, cols)
vis2[i] = make([]bool, cols)
for j := range grid[i] {
fmt.Scan(&grid[i][j])
}
}
for i := 0; i < rows; i++ {
bfs(i, 0, grid, vis1)
bfs(i, cols-1, grid, vis2)
}
for j := 0; j < cols; j++ {
bfs(0, j, grid, vis1)
bfs(rows-1, j, grid, vis2)
}
for i := range grid {
for j := range grid[i] {
if vis1[i][j] && vis2[i][j] {
fmt.Printf("%d %d\n", i, j)
}
}
}
}
func bfs(x, y int, grid [][]int, vis [][]bool) {
q := []point{{x, y}}
vis[x][y] = true
for len(q) > 0 {
p := q[0]
q = q[1:]
for _, d := range dirs {
nx, ny := p.x+d[0], p.y+d[1]
if nx >= 0 && nx < len(grid) && ny >= 0 && ny < len(grid[0]) {
if grid[nx][ny] >= grid[p.x][p.y] && !vis[nx][ny] {
vis[nx][ny] = true
q = append(q, point{nx, ny})
}
}
}
}
}
Maximum Island Construction
package main
import "fmt"
var dirs = [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func main() {
var rows, cols int
fmt.Scanln(&rows, &cols)
grid := make([][]int, rows)
vis := make([][]bool, rows)
islands := make(map[int]int)
for i := range grid {
grid[i] = make([]int, cols)
vis[i] = make([]bool, cols)
for j := range grid[i] {
fmt.Scan(&grid[i][j])
}
}
id := 2
for i := range grid {
for j := range grid[i] {
if grid[i][j] == 1 && !vis[i][j] {
area := 0
mark(i, j, id, grid, vis, &area)
islands[id] = area
id++
}
}
}
maxArea := 0
for _, a := range islands {
if a > maxArea {
maxArea = a
}
}
for i := range grid {
for j := range grid[i] {
if grid[i][j] == 0 {
connected := make(map[int]bool)
tempArea := 1
for _, d := range dirs {
ni, nj := i+d[0], j+d[1]
if ni >= 0 && ni < rows && nj >= 0 && nj < cols {
if grid[ni][nj] > 1 && !connected[grid[ni][nj]] {
tempArea += islands[grid[ni][nj]]
connected[grid[ni][nj]] = true
}
}
}
if tempArea > maxArea {
maxArea = tempArea
}
}
}
}
fmt.Println(maxArea)
}
func mark(x, y, id int, grid [][]int, vis [][]bool, area *int) {
vis[x][y] = true
grid[x][y] = id
*area++
for _, d := range dirs {
nx, ny := x+d[0], y+d[1]
if nx >= 0 && nx < len(grid) && ny >= 0 && ny < len(grid[0]) {
if grid[nx][ny] == 1 && !vis[nx][ny] {
mark(nx, ny, id, grid, vis, area)
}
}
}
}
String Transformation Chain
package main
import "fmt"
func main() {
var n int
fmt.Scanln(&n)
var start, end string
fmt.Scanln(&start, &end)
words := make([]string, n+2)
wordMap := make(map[string]int)
words[0] = start
words[1] = end
wordMap[start] = 0
wordMap[end] = 1
for i := 2; i < n+2; i++ {
fmt.Scanln(&words[i])
wordMap[words[i]] = i
}
if start == end {
fmt.Println(0)
return
}
graph := make([][]bool, n+2)
for i := range graph {
graph[i] = make([]bool, n+2)
}
for i := range words {
for j := i + 1; j < len(words); j++ {
if diffOne(words[i], words[j]) {
graph[i][j] = true
graph[j][i] = true
}
}
}
steps := findPath(graph, 0, 1)
fmt.Println(steps)
}
func diffOne(a, b string) bool {
count := 0
for i := range a {
if a[i] != b[i] {
count++
}
}
return count == 1
}
func findPath(graph [][]bool, start, end int) int {
visited := make([]bool, len(graph))
queue := []int{start}
steps := 1
for len(queue) > 0 {
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
current := queue[i]
if current == end {
return steps
}
for neighbor, connected := range graph[current] {
if connected && !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
queue = queue[levelSize:]
steps++
}
return 0
}
Directed Graph Reachability
package main
import "fmt"
func main() {
var nodes, edges int
fmt.Scanln(&nodes, &edges)
graph := make([][]bool, nodes+1)
for i := range graph {
graph[i] = make([]bool, nodes+1)
}
for i := 0; i < edges; i++ {
var from, to int
fmt.Scanln(&from, &to)
graph[from][to] = true
}
reachable := checkReachability(graph, 1)
if reachable == nodes {
fmt.Println(1)
} else {
fmt.Println(-1)
}
}
func checkReachability(graph [][]bool, start int) int {
visited := make([]bool, len(graph))
queue := []int{start}
visited[start] = true
count := 1
for len(queue) > 0 {
current := queue[0]
queue = queue[1:]
for neighbor := range graph {
if graph[current][neighbor] && !visited[neighbor] {
visited[neighbor] = true
count++
queue = append(queue, neighbor)
}
}
}
return count
}
Island Perimteer Calculation
package main
import "fmt"
var dirs = [4][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
func main() {
var rows, cols int
fmt.Scanln(&rows, &cols)
grid := make([][]int, rows)
for i := range grid {
grid[i] = make([]int, cols)
for j := range grid[i] {
fmt.Scan(&grid[i][j])
}
}
perimeter := 0
for i := range grid {
for j := range grid[i] {
if grid[i][j] == 1 {
perimeter += countEdges(i, j, grid)
}
}
}
fmt.Println(perimeter)
}
func countEdges(x, y int, grid [][]int) int {
edges := 4
for _, d := range dirs {
nx, ny := x+d[0], y+d[1]
if nx >= 0 && nx < len(grid) && ny >= 0 && ny < len(grid[0]) {
if grid[nx][ny] == 1 {
edges--
}
}
}
return edges
}