Submission #2070595


Source Code Expand

package main

import (
	"fmt"
	"strconv"
)

var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

type Point struct {
	x, y int
}

func main() {
	var H, W, K int
	fmt.Scan(&H, &W, &K)
	s := make([]int, H*W)
	var str string
	for i := 0; i < H; i++ {
		fmt.Scan(&str)
		for j := 0; j < W; j++ {
			s[i*H+j], _ = strconv.Atoi(string(str[j]))
		}
	}
	used := make([]bool, H*W)
	ans := make([]Point, 0)
	for l := 0; l < 10; l++ {
		for h := 0; h < H; h++ {
			for w := 0; w < W; w++ {
				p := h*H + w
				if !used[p] && s[p] != 0 {
					points := make([]Point, 0)
					points = append(points, Point{w, h})
					used[h*H+w] = true
					x := w
					y := h
					for {
						maxN := 0
						maxX := 0
						maxY := 0
						for i := 0; i < 4; i++ {
							nx := x + dx[i]
							ny := y + dy[i]
							if nx < 0 || nx >= W || ny < 0 || ny >= H {
								continue
							}
							if !used[ny*H+nx] && s[ny*H+nx] > 0 {
								if maxN < s[ny*H+nx] {
									maxN = s[ny*H+nx]
									maxX = nx
									maxY = ny
								}
							}
						}
						if maxN > 0 {
							points = append(points, Point{maxX, maxY})
							used[maxY*H+maxX] = true
						} else {
							for _, p := range points {
								used[p.y*H+p.x] = false
							}
							break
						}
						if len(points) == K {
							for pi := range points {
								ans = append(ans, points[pi])
								used[pi] = true
							}
							break
						}
						x = maxX
						y = maxY
					}
				}
			}
		}
	}
	// log.Println(len(ans))
	fmt.Println(len(ans) / K)
	for _, a := range ans {
		fmt.Println(a.y+1, a.x+1)
	}
}

Submission Info

Submission Time
Task A - Multiple Pieces
User fmhr
Language Go (1.6)
Score 167775
Code Size 1649 Byte
Status AC
Exec Time 9 ms
Memory 1280 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 17797 / 1343058 14871 / 1343058 16694 / 1343058 14146 / 1343058 17901 / 1343058 17329 / 1343058 16056 / 1343058 14919 / 1343058 16141 / 1343058 21921 / 1343058
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 9 ms 1280 KB
subtask_01_02.txt AC 9 ms 1152 KB
subtask_01_03.txt AC 9 ms 1152 KB
subtask_01_04.txt AC 9 ms 1280 KB
subtask_01_05.txt AC 9 ms 1152 KB
subtask_01_06.txt AC 9 ms 1152 KB
subtask_01_07.txt AC 9 ms 1152 KB
subtask_01_08.txt AC 9 ms 1152 KB
subtask_01_09.txt AC 9 ms 1280 KB
subtask_01_10.txt AC 9 ms 1152 KB