SHARE
TWEET

Untitled

a guest May 21st, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
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