結果

問題 No.421 しろくろチョコレート
コンテスト
ユーザー obakyan
提出日時 2020-04-26 00:15:07
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 71 ms / 2,000 ms
コード長 3,773 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 6,940 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-23 07:25:33
合計ジャッジ時間 2,330 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

local WhiteBlack = {}

WhiteBlack.create = function(self)
  self.edge = {}
  self.invedge = {}
  self.leftnode = {}
  self.rightmatched = {}
end

WhiteBlack.addNode = function(self, node, isLeft)
  if isLeft then
    self.leftnode[node] = true
    self.edge[node] = {}
  else
    self.invedge[node] = {}
  end
end

WhiteBlack.addEdge = function(self, src, dst)
  assert(self.leftnode[src])
  self.edge[src][dst] = 1
  self.invedge[dst][src] = 0
end

WhiteBlack.run = function(self, spos)
  local tasks = {spos}
  local tasked = {}
  local dstpos = 0
  tasked[spos] = true
  local len = {}
  len[spos] = 0
  local found = false
  while 0 < #tasks do
    local src = tasks[#tasks]
    table.remove(tasks)
    tasked[src] = false
    if self.leftnode[src] then
      for dst, c in pairs(self.edge[src]) do
        if c == 1 and (not len[dst] or len[src] + 1 < len[dst]) then
          len[dst] = len[src] + 1
          if not self.rightmatched[dst] then
            self.rightmatched[dst] = true
            found = true
            dstpos = dst
            break
          elseif not tasked[dst] then
            table.insert(tasks, dst)
            tasked[dst] = true
          end
        end
      end
    else
      if self.invedge[src] then
        for dst, c in pairs(self.invedge[src]) do
          if c == 1 and (not len[dst] or len[src] + 1 < len[dst]) then
            len[dst] = len[src] + 1
            if not tasked[dst] then
              table.insert(tasks, dst)
              tasked[dst] = true
            end
          end
        end
      end
    end
    if found then break end
  end
  if found then
    local l = len[dstpos]
    for i = l, 1, -1 do
      if i % 2 == 1 then
        for src, _u in pairs(self.invedge[dstpos]) do
          if self.edge[src][dstpos] == 1 and len[src] == i - 1 then
            self.edge[src][dstpos] = 0
            self.invedge[dstpos][src] = 1
            dstpos = src
            break
          end
        end
      else
        for src, _u in pairs(self.edge[dstpos]) do
          if self.invedge[src][dstpos] == 1 and len[src] == i - 1 then
            self.invedge[src][dstpos] = 0
            self.edge[dstpos][src] = 1
            dstpos = src
            break
          end
        end
      end
    end
    return true
  else return false end
end

WhiteBlack.getMatchCount = function(self)
  local cnt = 0
  for src, _u in pairs(self.leftnode) do
    local res = self:run(src)
    if res then cnt = cnt + 1 end
  end
  return cnt
end

WhiteBlack.new = function()
  local obj = {}
  setmetatable(obj, {__index = WhiteBlack})
  obj:create()
  return obj
end

local h, w = io.read("*n", "*n", "*l")
local map = {}
local wb = WhiteBlack.new()
local wcnt, bcnt = 0, 0
for i = 1, h do
  local s = io.read()
  for j = 1, w do
    local idx = (i - 1) * w + j
    if s:sub(j, j) == "." then
      map[idx] = false
    else
      map[idx] = true
      if (i + j) % 2 == 0 then
        wcnt = wcnt + 1
        wb:addNode(idx, true)
      else
        bcnt = bcnt + 1
        wb:addNode(idx, false)
      end
    end
  end
end
for i = 1, h do
  for j = 1, w - 1 do
    local idx = (i - 1) * w + j
    if map[idx] and map[idx + 1] then
      if (i + j) % 2 == 0 then
        wb:addEdge(idx, idx + 1)
      else
        wb:addEdge(idx + 1, idx)
      end
    end
  end
end
for j = 1, w do
  for i = 1, h - 1 do
    local idx = (i - 1) * w + j
    if map[idx] and map[idx + w] then
      if (i + j) % 2 == 0 then
        wb:addEdge(idx, idx + w)
      else
        wb:addEdge(idx + w, idx)
      end
    end
  end
end
local matched = wb:getMatchCount()
wcnt, bcnt = wcnt - matched, bcnt - matched
local paired = math.min(wcnt, bcnt)
wcnt, bcnt = wcnt - paired, bcnt - paired
print(matched * 100 + paired * 10 + wcnt + bcnt)
0