結果

問題 No.157 2つの空洞
ユーザー yozayoza
提出日時 2015-02-27 03:07:24
言語 Nim
(2.2.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,388 bytes
コンパイル時間 3,689 ms
コンパイル使用メモリ 66,304 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-28 22:24:43
合計ジャッジ時間 4,325 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 39) Warning: imported and not used: 'math' [UnusedImport]
/home/judge/data/code/Main.nim(1, 28) Warning: imported and not used: 'algorithm' [UnusedImport]

ソースコード

diff # 

import strutils, sequtils, algorithm, math

var
  wh = split(readLine(stdin), ' ').map(parseInt)
  count = 0
  board = newSeq[seq[int]](wh[1])
  cave_points1 = newSeq[seq[int]](0)
  cave_points2 = newSeq[seq[int]](0)
  dire = [[0, -1], [1, 0], [0, 1], [-1, 0]]
  pre = 0
  min_v = high(int)

proc init(pre: var int; x, y: int) =
  if pre == 0:
    for i in countup(1, wh[1] - 2):
      for j in countup(1, wh[0] - 2):
        if board[i][j] == 0:
          pre += 1
          board[i][j] = pre
          if pre == 1:
            cave_points1.add(@[i,j])
          else:
            cave_points2.add(@[i,j])
          for d in dire:
            init(pre, j + d[0], i + d[1])
  else:
    if board[y][x] == 0:
      board[y][x] = pre
      if pre == 1:
        cave_points1.add(@[y,x])
      else:
        cave_points2.add(@[y,x])
      for d in dire:
        if 0 < x + d[0] and x + d[0] < wh[0] - 1 and 0 < y + d[1] and y + d[1] < wh[1] - 1:
          init(pre, x + d[0], y + d[1])

for i in countup(0, wh[1] - 1):
  var line = readLine(stdin)
  var row = newSeq[char](0)
  for c in line:
    row.add(c)
  board[i] = row.map(proc (x: char): int =
                       result = if x == '#': -1 else: 0
                       return)

init(pre, 1, 1)

for po1 in cave_points1:
  for po2 in cave_points2:
    min_v = min(min_v, abs(po1[1] - po2[1]) + abs(po1[0] - po2[0]) - 1)

echo(min_v)
0