daily pastebin goal
22%
SHARE
TWEET

Untitled

a guest Jun 3rd, 2018 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import "fmt"
  4.  
  5. type Triplet struct {
  6.     first int
  7.     second int
  8.     third string
  9. }
  10.  
  11. type Pair struct {
  12.     one []int
  13.     two string
  14. }
  15.  
  16. func PrintMe(mas []Triplet, n int, m int, final []int) {
  17.     for i:=0; i<m; i++ {
  18.         fmt.Print(mas[i].first, " ")
  19.         fmt.Print(mas[i].second, " ")
  20.         fmt.Println(mas[i].third)
  21.     }
  22.     for i:=0; i<n; i++ {
  23.         fmt.Print(final[i], " ")
  24.     }
  25.     fmt.Println()
  26. }
  27.  
  28. func NewSet(n int) ([]int) {
  29.     c := make([]int, n)
  30.     for i:=0; i<n; i++ {
  31.         c[i] = -1
  32.     }
  33.     return c
  34. }
  35.  
  36. func Closure(mas []Triplet, z []int) ([]int) {
  37.     C := NewSet(len(mas))
  38.     //fmt.Println("z = ", z)
  39.     for q:=0; q<len(z); q++ {
  40.         if z[q] != -1 {
  41.             DFS(mas, z[q], C)
  42.         }
  43.     }
  44.     return C
  45. }
  46.  
  47. func DFS(mas []Triplet, q int, C []int) {
  48.     //fmt.Println("q = ", q)
  49.     //fmt.Println("CB = ", C)
  50.     if !Search(C, q) {  //если q не принадлежит С
  51.         for i:=0; i<len(C); i++ {
  52.             if C[i] == -1 { //если первый элемент С пустой,
  53.                 C[i] = q    //кидаю туда q
  54.                 break
  55.             }
  56.         }
  57.         //fmt.Println("CD = ", C)
  58.         for i:=0; i<len(mas); i++ {
  59.             if mas[i].first == q && mas[i].third == "lambda" {
  60.                 DFS(mas, mas[i].second, C)
  61.             }
  62.         }
  63.     }
  64. }
  65.  
  66. func Search(Qn []int, qn int) (bool) {
  67.     var eq bool
  68.     for i:= range Qn {
  69.         if Qn[i] == qn {
  70.             eq = true
  71.             break
  72.         }
  73.     }
  74.     return eq
  75. }
  76.  
  77. func newStack(n int) ([][]int)  {
  78.     stack := make([][]int, n, n)
  79.     for i:=0; i<n; i++ {
  80.         stack[i] = make([]int, n)
  81.     }
  82.     for i:=0; i<n; i++ {
  83.         for j:=0; j<n; j++ {
  84.             stack[i][j] = -1
  85.         }
  86.     }
  87.     return stack
  88. }
  89.  
  90. func Pop(stack [][]int) ([]int) {
  91.     for i:=len(stack)-1; i>=0; i-- {
  92.         //fmt.Println("!", i)
  93.         if stack[i][0] != -1 {
  94.             return stack[i]
  95.         }
  96.     }
  97.     return nil
  98. }
  99.  
  100. func Det(mas []Triplet, Final []int, q int) {
  101.     n := len(mas)
  102.     l:=1
  103.     z:=make([]int, n)
  104.     for i:=0; i<n; i++ {
  105.         z[i] = -1
  106.     }
  107.     z[0] = q
  108.     qo := Closure(mas, z)
  109.     delta := make([]Pair, n)
  110.     for i:=0; i<n; i++ {
  111.         delta[i].one = append(delta[i].one, -1)
  112.     }
  113.     F := make([][]int, n, n)
  114.     for i:=0; i<n; i++ {
  115.         F[i] = make([]int, n)
  116.     }
  117.     for i:=0; i<n; i++ {
  118.         for j:=0; j<n; j++ {
  119.             F[i][j] = -1
  120.         }
  121.     }
  122.     Q := make([][]int, n, n)
  123.     for i:=0; i<n; i++ {
  124.         Q[i] = make([]int, n)
  125.     }
  126.     for i:=0; i<n; i++ {
  127.         for j:=0; j<n; j++ {
  128.             Q[i][j] = -1
  129.         }
  130.     }
  131.     for i:=0; i<len(qo); i++ {
  132.         Q[0][i] = qo[i]
  133.         //fmt.Println(Q[i])
  134.     }
  135.     stack := newStack(n)
  136.     for i:=0; i<len(qo); i++ {
  137.         stack[0][i] = qo[i]
  138.     }
  139.     stackSize := 1
  140.     for stackSize > 0 {
  141.         zz := Pop(stack)
  142.         fmt.Println("zz = ",zz)
  143.         for u:=0; u<len(zz); u++ {
  144.             if Final[u] == 1 {
  145.                 for i:=0; i<len(F); i++ {
  146.                     if F[i][0] != -1 {
  147.                         F[i] = zz
  148.                         break
  149.                     }
  150.                 }
  151.                 break
  152.             }
  153.         }
  154.         hh := make([]int, n)
  155.         for i:=0; i<n; i++ {
  156.             hh[i] = -1
  157.         }
  158.         start:=0
  159.         for a:=0; a<n; a++ {
  160.             help := mas[a].third
  161.             for i := 0; i < n; i++ {
  162.                 if help == mas[i].third && Search(zz, mas[i].first){
  163.                     hh[start] = mas[i].second
  164.                     start++
  165.                 }
  166.             }
  167.             //fmt.Println("hh[", help, "] = ", hh)
  168.  
  169.             zzz := Closure(mas, hh)
  170.             eq := true
  171.             for i := 0; i < n; i++ {
  172.                 for j := 0; j < n; j++ {
  173.                     if zzz[j] != Q[i][j] {
  174.                         eq = false
  175.                     } else {
  176.                         eq = true
  177.                     }
  178.                 }
  179.             }
  180.             if !eq {
  181.                 for i := 0; i < n; i++ {
  182.                     if Q[i][0] != -1 {
  183.                         for j := 0; j < len(zzz); j++ {
  184.                             Q[i][j] = zzz[j]
  185.                         }
  186.                     }
  187.                 }
  188.                 for i := 0; i < len(zzz); i++ {
  189.                     stack[stackSize][i] = zzz[i]
  190.                 }
  191.             }
  192.             fmt.Println("!!!!!!!!!!!a = ", a)
  193.             fmt.Println("help = ", help)
  194.             fmt.Println("zzz = ", zzz)
  195.             delta[0].one = zz
  196.             delta[0].two = "hren"
  197.             fmt.Println("l = ", l)
  198.             if l < n {
  199.                 delta[l].one = zzz
  200.                 delta[l].two = help
  201.                 l++
  202.             }
  203.             for i:=0; i<n; i++ {
  204.                 hh[i] = -1
  205.             }
  206.             start = 0
  207.             stackSize--
  208.         }
  209.     }
  210.     for i:=0; i<n; i++ {
  211.         for j:=0; j<n; j++ {
  212.             if delta[i].one[j] != -1 {
  213.                 fmt.Print(delta[i].one[j], " ")
  214.             }
  215.         }
  216.         fmt.Print(delta[i].two, " ")
  217.         fmt.Println()
  218.     }
  219.     //fmt.Println("det : ", delta)
  220.  
  221. }
  222.  
  223. func main() {
  224.     var n, m, q int
  225.  
  226.     fmt.Scan(&n)
  227.     fmt.Scan(&m)
  228.  
  229.     mas := make([]Triplet, m)
  230.  
  231.     for i:=0; i<m; i++ {
  232.         fmt.Scan(&mas[i].first)
  233.         fmt.Scan(&mas[i].second)
  234.         fmt.Scan(&mas[i].third)
  235.     }
  236.  
  237.     final := make([]int, n)
  238.  
  239.     for i:=0; i<n; i++ {
  240.         fmt.Scan(&final[i])
  241.     }
  242.     fmt.Scan(&q)
  243.  
  244.     //PrintMe(mas, n, m, final)
  245.  
  246.     //C:= Closure(mas, n, z)
  247.     //fmt.Print("C = ",C)
  248.     Det(mas, final, q)
  249. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top