Advertisement
Guest User

Untitled

a guest
May 21st, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.82 KB | None | 0 0
  1. package main
  2.  
  3. import (
  4. "bufio"
  5. "fmt"
  6. "io"
  7. "os"
  8. "strconv"
  9. "strings"
  10. )
  11.  
  12. // Complete the connectedCell function below.
  13. func connectedCell(matrix [][]int32) int32 {
  14. var max int32 = 0
  15. visited := make([][]bool, len(matrix))
  16. for i:=0; i<len(matrix); i++{
  17. visited[i] = make([]bool, len(matrix[0]))
  18. }
  19. for i:=0; i<len(matrix); i++{
  20. for j:=0; j<len(matrix[0]); j++{
  21. if(matrix[i][j]==1 && !visited[i][j]){
  22. count := DFS(matrix, visited, i, j)
  23. if count > max{
  24. max = count
  25. }
  26. }
  27. }
  28. }
  29. return max
  30. }
  31.  
  32. func DFS(matrix [][]int32, visited [][]bool, i int, j int) int32{
  33. var count int32 = 1
  34. visited[i][j] = true
  35. for m:=-1;m<=1;m+=1{
  36. for n:=-1;n<=1;n+=1{
  37. if m==0 && n==0 {
  38. continue
  39. }
  40. DFSVisit(matrix, visited, i+m, j+n, &count)
  41. }
  42. }
  43. return count
  44. }
  45.  
  46. func DFSVisit(matrix [][]int32, visited [][]bool, i int, j int, count *int32){
  47. if i<0 || j<0 || i>=len(matrix) || j>=len(matrix[0]) || matrix[i][j] == 0 || visited[i][j]{
  48. return
  49. }
  50. visited[i][j] = true
  51. *count += 1
  52. for m:=-1;m<=1;m++{
  53. for n:=-1;n<=1;n++{
  54. if m == 0 && n == 0{
  55. continue
  56. }
  57. DFSVisit(matrix, visited, i+m, j+n, count)
  58. }
  59. }
  60. }
  61.  
  62. func main() {
  63. reader := bufio.NewReaderSize(os.Stdin, 1024 * 1024)
  64.  
  65. stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
  66. checkError(err)
  67.  
  68. defer stdout.Close()
  69.  
  70. writer := bufio.NewWriterSize(stdout, 1024 * 1024)
  71.  
  72. nTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
  73. checkError(err)
  74. n := int32(nTemp)
  75.  
  76. mTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
  77. checkError(err)
  78. m := int32(mTemp)
  79.  
  80. var matrix [][]int32
  81. for i := 0; i < int(n); i++ {
  82. matrixRowTemp := strings.Split(readLine(reader), " ")
  83.  
  84. var matrixRow []int32
  85. for _, matrixRowItem := range matrixRowTemp {
  86. matrixItemTemp, err := strconv.ParseInt(matrixRowItem, 10, 64)
  87. checkError(err)
  88. matrixItem := int32(matrixItemTemp)
  89. matrixRow = append(matrixRow, matrixItem)
  90. }
  91.  
  92. if len(matrixRow) != int(int(m)) {
  93. panic("Bad input")
  94. }
  95.  
  96. matrix = append(matrix, matrixRow)
  97. }
  98.  
  99. result := connectedCell(matrix)
  100.  
  101. fmt.Fprintf(writer, "%d\n", result)
  102.  
  103. writer.Flush()
  104. }
  105.  
  106. func readLine(reader *bufio.Reader) string {
  107. str, _, err := reader.ReadLine()
  108. if err == io.EOF {
  109. return ""
  110. }
  111.  
  112. return strings.TrimRight(string(str), "\r\n")
  113. }
  114.  
  115. func checkError(err error) {
  116. if err != nil {
  117. panic(err)
  118. }
  119. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement