Advertisement
Kambar_Z

Generate lattice paths

Feb 19th, 2022
1,433
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Go 1.63 KB | None | 0 0
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5. )
  6.  
  7. var (
  8.     ways  = make([][][]rune, 0)
  9.     count int
  10. )
  11.  
  12. func rev(matrix [][]rune) [][]rune {
  13.     new := defaultMatrix(len(matrix))
  14.     for i := 0; i < len(matrix); i++ {
  15.         for j := 0; j < len(matrix[i]); j++ {
  16.             new[len(matrix)-i-1][j] = matrix[i][j]
  17.         }
  18.     }
  19.     return new
  20. }
  21.  
  22. func copy(matrix [][]rune) [][]rune {
  23.     duplicate := make([][]rune, len(matrix))
  24.     for i := 0; i < len(matrix); i++ {
  25.         duplicate[i] = make([]rune, len(matrix[0]))
  26.         for j := 0; j < len(matrix[0]); j++ {
  27.             duplicate[i][j] = matrix[i][j]
  28.         }
  29.     }
  30.     return duplicate
  31. }
  32.  
  33. func rec(i, j int, current [][]rune) {
  34.     if i < len(current) && j < len(current[0]) {
  35.         current[i][j] = '#'
  36.     }
  37.     if i == len(current)-1 && j == len(current[0])-1 {
  38.         new := copy(current)
  39.         ways = append(ways, new)
  40.         printMatrix(new)
  41.         return
  42.     }
  43.     if j < len(current[0]) {
  44.         new := copy(current)
  45.         rec(i+1, j, new)
  46.     }
  47.     if j < len(current[0]) {
  48.         new := copy(current)
  49.         rec(i, j+1, new)
  50.     }
  51. }
  52.  
  53. func printMatrix(slice [][]rune) {
  54.     slice = rev(slice)
  55.     count++
  56.     fmt.Printf("[%d]\n", count)
  57.     for i := 0; i < len(slice); i++ {
  58.         for j := 0; j < len(slice[i]); j++ {
  59.             fmt.Print(string(slice[i][j]))
  60.         }
  61.         fmt.Println()
  62.     }
  63.     fmt.Println()
  64. }
  65.  
  66. func defaultMatrix(n int) [][]rune {
  67.     matrix := make([][]rune, n)
  68.     for i := 0; i < n; i++ {
  69.         matrix[i] = make([]rune, n)
  70.         for j := 0; j < n; j++ {
  71.             if j >= i {
  72.                 matrix[i][j] = '.'
  73.             } else {
  74.                 matrix[i][j] = ' '
  75.             }
  76.         }
  77.     }
  78.     matrix[0][0] = ' '
  79.     return matrix
  80. }
  81.  
  82. func main() {
  83.     var n int
  84.     fmt.Scanf("%d", &n)
  85.  
  86.     initial := defaultMatrix(n)
  87.     rec(0, 1, initial)
  88.     fmt.Println(len(ways))
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement