Drkcore

08 09 2011 Go Tweet

GoでDFS

プログラミングコンテストチャレンジブック2-1のLake Counting

ProductName プログラミングコンテストチャレンジブック
秋葉 拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )


次のような水たまり(Wで八方向に繋がっている)の数を数える

W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

コード

package main

import "fmt"

const MAX_N = 100
const MAX_M = 100
var N,M int

func makeTable(lake []byte, field *[MAX_N][MAX_M]byte, width,height int) {

    for y := 0; y < height; y++ {
        for x := 0; x < width; x++ {
            field[y][x] = lake[y*width+x]
        }
    }
}

func dfs (field *[MAX_N][MAX_M]byte, x, y int) {
    var nx,ny int
    field[x][y] = '.'
    for dx := -1; dx <= 1; dx++ {
        for dy := -1; dy <= 1; dy++ {
            nx = x + dx
            ny = y + dy
            if 0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W' {
                dfs(field, nx, ny)
            }
        }
    }
}

func main() {
    N = 10
    M = 12
    res := 0
    field := new([MAX_N][MAX_M]byte)

    lake := []byte("W........WW..WWW.....WWW....WW...WW\
    ..........WW..........W....W......W...W.W.....WW.W.\
    W.W.....W..W.W......W...W.......W.")

    makeTable(lake,field,M,N)

    for i := 0; i<N; i ++ {
        for j :=0; j<M; j++ {
            if field[i][j] == 'W' {
                dfs(field, i, j)
                res++
            }
        }
    }
    fmt.Printf("result: %d\n", res)
}

Goにはpermutationとかあんのかなぁとふと思った。

About

  • もう5年目(wishlistありマス♡)
  • 最近はPythonとDeepLearning
  • 日本酒自粛中
  • ドラムンベースからミニマルまで
  • ポケモンGOゆるめ

Tag

Python Deep Learning javascript chemoinformatics Emacs sake and more...

Ad

© kzfm 2003-2021