Submission #1400920


Source Code Expand

# http://rco-contest-2017-qual.contest.atcoder.jp/tasks/rco_contest_2017_qual_a

class PieceCalculator
  def initialize(h, w, k, ary)
    @did_pieces = []
    @H = h
    @W = w
    @K = k
    @ary = ary
  end

  def create_pieces
    pieces = []
    missed_count = 0
    while missed_count < 100
      piece = create_piece
      if !piece.nil?
        pieces << piece
      else
        missed_count += 1
      end
    end
    pieces
  end

  # pieceを作成する
  def create_piece
    start = get_start_point
    piece = [start]
    @did_pieces << start
    (0...7).each{
      neighbors = find_neighbors(piece)
      if neighbors.length == 0
        @did_pieces = @did_pieces - piece
        return nil
      else
        selected = neighbors.first
        neighbors.each{ |v|
          i, j = v[0], v[1]
          i_now, j_now = selected[0], selected[1]
          if @ary[i][j] > @ary[i_now][j_now]
            selected = [i, j]
          end
        }
        piece << selected
        @did_pieces << selected
      end
    }
    piece
  end

  def get_start_point
    i, j = rand(@H), rand(@W)
    while @ary[i][j] == 0 || (@did_pieces != [] && @did_pieces.include?([i, j]))
      i, j = rand(@H), rand(@W)
    end
    [i, j]
  end

  # ピース隣接するマスを返す
  def find_neighbors(piece)
    neighbors = []
    piece.each{ |ary|
      i, j = ary[0], ary[1]
      neighbors << [i+1, j] if i+1 < 50 && @ary[i+1, j] != 0
      neighbors << [i-1, j] if 0 <= i-1 && @ary[i-1, j] != 0
      neighbors << [i, j+1] if j+1 < 50 && @ary[i, j+1] != 0
      neighbors << [i, j-1] if 0 <= j-1 && @ary[i, j-1] != 0
    }
    piece.each{ |ary|
      neighbers = neighbors - ary
    }
    neighbors - @did_pieces
  end
end

# ピースの出力
def print_pieces(pieces)
  puts pieces.length
  pieces.each{ |piece|
    piece.each{ |ary|
      puts "#{ary[0]+1} #{ary[1]+1}"
    }
  }
end

H, W, K = gets.split(" ").map(&:to_i)

ary = []
(0...H).each{
  ary << gets.split("").map(&:to_i)
}

pc = PieceCalculator.new(H, W, K, ary)

pieces = []
pieces = pc.create_pieces

print_pieces(pieces)

Submission Info

Submission Time
Task A - Multiple Pieces
User mitsu9
Language Ruby (2.3.3)
Score 540712
Code Size 2194 Byte
Status AC
Exec Time 4984 ms
Memory 3580 KB

Compile Error

./Main.rb:71: warning: assigned but unused variable - neighbers

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 56819 / 1343058 47585 / 1343058 56290 / 1343058 46913 / 1343058 58413 / 1343058 55971 / 1343058 52774 / 1343058 48998 / 1343058 56807 / 1343058 60142 / 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 4618 ms 3580 KB
subtask_01_02.txt AC 4984 ms 3580 KB
subtask_01_03.txt AC 4617 ms 3580 KB
subtask_01_04.txt AC 4622 ms 3580 KB
subtask_01_05.txt AC 4668 ms 3452 KB
subtask_01_06.txt AC 4591 ms 3452 KB
subtask_01_07.txt AC 4750 ms 3580 KB
subtask_01_08.txt AC 4492 ms 3580 KB
subtask_01_09.txt AC 4736 ms 3452 KB
subtask_01_10.txt AC 4786 ms 3580 KB