fork download
copy 
  1. 	rei = [
  2. 		[	# ex 1
  3. 			[1,1,1,1,1,0,1],
  4. 			[1,0,0,0,1,0,1],
  5. 			[1,0,1,0,1,0,1],
  6. 			[1,0,0,0,1,0,1],
  7. 			[1,1,1,1,0,1,1],
  8. 			[0,0,0,0,0,0,0],
  9. 			[0,0,1,1,1,1,1],
  10. 		],
  11. 		[	# ex 2
  12. 			[1,1,1,1,1,1,1],
  13. 			[0,0,0,0,0,0,0],
  14. 			[1,1,1,1,1,0,1],
  15. 			[1,0,0,0,1,0,1],
  16. 			[1,0,1,0,1,1,1],
  17. 			[1,0,0,0,1,0,1],
  18. 			[1,1,1,1,1,0,1],
  19. 		],
  20. 	]
  21.  
  22. boards =
  23. [[[0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  24.   [0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
  25.   [0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
  26.   [0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
  27.   [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
  28.   [0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
  29.   [0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  30.   [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
  31.   [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1],
  32.   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
  33.   [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  34.   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1],
  35.   [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  36.   [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1],
  37.   [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0],
  38.   [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1],
  39.   [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1],
  40.   [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0],
  41.   [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0],
  42.   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0]],
  43.  [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
  44.   [1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1],
  45.   [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
  46.   [1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1],
  47.   [1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
  48.   [1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1],
  49.   [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  50.   [0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
  51.   [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  52.   [0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  53.   [0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
  54.   [0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0],
  55.   [0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0],
  56.   [0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0],
  57.   [0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0],
  58.   [0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0],
  59.   [0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0],
  60.   [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0],
  61.   [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  62.   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
  63.  [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  64.   [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
  65.   [0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0],
  66.   [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
  67.   [0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0],
  68.   [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
  69.   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  70.   [0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0],
  71.   [0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0],
  72.   [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0],
  73.   [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0],
  74.   [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0],
  75.   [0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0],
  76.   [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0],
  77.   [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0],
  78.   [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0],
  79.   [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0],
  80.   [0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0],
  81.   [0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0],
  82.   [0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0]]]
  83.  
  84. def putBoard( board )
  85. 	board.size.times{|y|
  86. 		print ' '
  87. 		board[y].size.times{|x|
  88. 			print case board[y][x]
  89. 			when -1; '・'
  90. 			when 0; '＃'
  91. 			when 1; '■'
  92. 			end
  93. 		}
  94. 		puts
  95. 	}
  96. 	puts
  97. end
  98.  
  99. def guardPaint( board, y, x )	# 斜め方向有り
  100. 	return	if board[y][x] != 0
  101. 	board[y][x] = -1
  102. 	guardPaint( board, y, x+1 )	if board[y][x+1] == 0
  103. 	guardPaint( board, y+1, x )	if board[y+1][x] == 0
  104. 	guardPaint( board, y, x-1 )	if board[y][x-1] == 0
  105. 	guardPaint( board, y-1, x )	if board[y-1][x] == 0
  106. 	guardPaint( board, y-1, x+1 )	if board[y-1][x+1] == 0
  107. 	guardPaint( board, y+1, x+1 )	if board[y+1][x+1] == 0
  108. 	guardPaint( board, y-1, x-1 )	if board[y-1][x-1] == 0
  109. 	guardPaint( board, y+1, x-1 )	if board[y+1][x-1] == 0
  110. end
  111.  
  112. def katamari( board, y, x, sum = 0 )	# 上下左右 4方向
  113. 	case board[y][x]
  114. 	when 0
  115. 	when 1;	sum += 1
  116. 	else
  117. 		return [board, sum]
  118. 	end
  119. 	board[y][x] = -1
  120.  
  121. 	board, sum = katamari( board, y, x+1, sum )	if board[y][x+1] >= 0
  122. 	board, sum = katamari( board, y+1, x, sum )	if board[y+1][x] >= 0
  123. 	board, sum = katamari( board, y, x-1, sum )	if board[y][x-1] >= 0
  124. 	board, sum = katamari( board, y-1, x, sum )	if board[y-1][x] >= 0
  125.  
  126. 	return [board, sum]
  127. end
  128.  
  129. def sol( board )
  130. # 番兵付加
  131. 	board.size.times{|y|
  132. 		board[y].unshift( -1 )
  133. 		board[y] << -1
  134. 	}
  135. 	x_len = board[0].size
  136. 	board.unshift( [-1] * x_len )
  137. 	board.push( [-1] * x_len )
  138. #	putBoard( board )
  139.  
  140. # 空白塗りつぶし(番兵)
  141. 	(board[1].size-2).times{|x|
  142. 		guardPaint( board, 1, x+1 )	if board[1][x+1] == 0
  143. 	}
  144. 	(board.size-2).times{|y|
  145. 		guardPaint( board, y+1, 1 )	if board[y+1][1] == 0
  146. 		x = board[y+1].size - 2
  147. 		guardPaint( board, y+1, x )	if board[y+1][x] == 0
  148. 	}
  149. 	y = board.size - 2
  150. 	(board[1].size-2).times{|x|
  151. 		guardPaint( board, y, x+1 )	if board[y][x+1] == 0
  152. 	}
  153.  
  154. # 塊作り
  155. 	maxSum = -1
  156. 	wrk = board.dup
  157. 	(wrk.size-2).times{|y|
  158. 		(wrk[1].size-2).times{|x|
  159. 			next if wrk[y+1][x+1] < 0
  160. 			sum = 0
  161. 			wrk, sum = katamari( wrk, y+1, x+1, sum )	
  162. 			maxSum = [maxSum,sum].max
  163. #			putBoard( wrk )
  164. #			p sum
  165. #			puts
  166. 		}
  167. 	}
  168.  
  169. #	putBoard( board )
  170. #	p maxSum
  171. #	puts "   #{board.size-2} * #{board[1].size-2}  "
  172. 	maxSum
  173. end
  174.  
  175. ##############################################################################
  176. # MAIN
  177.  
  178. 	puts "example"
  179. 	print "1:",  sol( rei[0] )
  180. 	print " 2:", sol( rei[1] )
  181. 	puts "\n\n"
  182.  
  183. 	sols = []
  184. 	boards.size.times{|no|
  185. 		sols << [ "#{no+1}:#{sol( boards[no] )}" ]
  186. 	}
  187. 	puts sols.join(' ')
  188.  
Success #stdin #stdout 0.01s 6540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
example
1:15 2:23

1:58 2:58 3:85
https://ideone.com/n1jLCH
Part19 520 塊
language:
Ruby (ruby 2.5.5)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!