paizaの見本問題 go言語 Sランク 島探し
go言語の解答例などは存在していないので、上げることにしました。
また、見本問題は解説や公開してもいいとのことで公開させていただいてます。
単純な問題だったので、特にコメントアウトで細かい補足はしていません。
実装方針としては
メイン関数で2次元のスライスを宣言、関数外からでも値を自由に操作できるように、ポインタ変数にしています。
不随するデータの方はcontent int, fl intでcontentは中身を保持用で値が参照されたかどうかと、countの数を入れるデータを入れています。
関数conでは、関数cを回すための土台を作っています。
contentが1かつまだ未参照の値(flが0)を見つけたときに関数cを実行します。
関数cは再帰関数かつ、ツリー状に関数を実行していきます。例えば
010
111
という値を見たとき、土台の関数conでは左上から右へそして下へ移動するようになっているので、まず初めに関数cが実行されるのは[0][1]となっています。
関数cでは上下左右を確認し、もし1があれがそちらに移動して再度関数cを実行するようなプログラムになっています。
package main
import "fmt"
type Data struct{
content int
fl int
}
var count = 0
func con(data *[][]Data, n int, m int) {
var pos =[2]int{n, m}
for i := 0; i < n ; i++{
for j := 0; j < m; j++{
if (*data)[i][j].content == 1 &&(*data)[i][j].fl == 0{
count++
c(data, pos,i,j)
// print((*data)[i][j].fl)
if (*data)[i][j].fl != 0{
continue
}
}
//int((*data)[i][j].fl)
//print(" ")
}
// print("\n")
}
fmt.Print(count)
}
func c(data *[][]Data, pos [2]int,cur_x,cur_y int) {
/*
print(cur_x + 1, cur_y + 1)
print(" ")
print((*data)[cur_x][cur_y].fl)
print(" ")
print(count)
print("\n")
*/
if (*data)[cur_x][cur_y].content == 1{
(*data)[cur_x][cur_y].fl = count
//flag into := {0, 0, 0}
if (cur_x + 1) != pos[0] && (*data)[cur_x + 1][cur_y].fl == 0 && (*data)[cur_x + 1][cur_y].content == 1{
// if((*data)[cur_x + 1][cur_y].content == 1){
c(data, pos, cur_x + 1, cur_y)
//flag.l = 1
// }
}
if (cur_x - 1) != -1 && (*data)[cur_x - 1][cur_y].fl == 0 && (*data)[cur_x - 1][cur_y].content == 1{
// if((*data)[cur_x + 1][cur_y].content == 1){
c(data, pos, cur_x - 1, cur_y)
//flag.l = 1
// }
}
// }
if (cur_y + 1) != pos[1] && (*data)[cur_x][cur_y + 1].content == 1 && (*data)[cur_x][cur_y + 1].fl == 0{
//if (*data)[cur_x][cur_y + 1].content == 1{
c(data, pos, cur_x, cur_y+ 1)
// }
}
if (cur_y - 1) != -1 && (*data)[cur_x][cur_y - 1].content == 1 && (*data)[cur_x][cur_y - 1].fl == 0{
//if (*data)[cur_x][cur_y + 1].content == 1{
c(data, pos, cur_x, cur_y - 1)
// }
}
}
}
func main(){
var m, n int
fmt.Scanf("%d %d\n", &m, &n)
var dum int
var a = make([][]Data, n)//2次元配列aの仮宣言
for i := 0; i < n ; i++ {
for j:=0; j < m; j++{
fmt.Scanf("%d", &dum)
ap := Data{content:dum, el:false, fl:0}
a[i] = append(a[i], ap)
}
}
con(&a, n, m)
}
//fmt.Print(con(a, n, m))