#471082 (Lua) No.421 しろくろチョコレート

• 問題: No.421 しろくろチョコレート
• ユーザー: 👑 obakyan
• 提出日時: 2020-04-26 00:15:07
• 言語: Lua (LuaJit 2.1.1696795921)
• 結果: 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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	11 ms; 6,944 KB
testcase_02	AC	5 ms; 6,944 KB
testcase_03	AC	3 ms; 6,944 KB
testcase_04	AC	4 ms; 6,944 KB
testcase_05	AC	6 ms; 6,940 KB
testcase_06	AC	3 ms; 6,940 KB
testcase_07	AC	10 ms; 6,944 KB
testcase_08	AC	4 ms; 6,940 KB
testcase_09	AC	6 ms; 6,940 KB
testcase_10	AC	5 ms; 6,944 KB
testcase_11	AC	9 ms; 6,940 KB
testcase_12	AC	1 ms; 6,940 KB
testcase_13	AC	1 ms; 6,940 KB
testcase_14	AC	2 ms; 6,944 KB
testcase_15	AC	1 ms; 6,940 KB
testcase_16	AC	12 ms; 6,944 KB
testcase_17	AC	16 ms; 6,940 KB
testcase_18	AC	19 ms; 6,940 KB
testcase_19	AC	1 ms; 6,940 KB
testcase_20	AC	10 ms; 6,948 KB
testcase_21	AC	14 ms; 6,940 KB
testcase_22	AC	10 ms; 6,940 KB
testcase_23	AC	2 ms; 6,944 KB
testcase_24	AC	2 ms; 6,940 KB
testcase_25	AC	1 ms; 6,944 KB
testcase_26	AC	1 ms; 6,944 KB
testcase_27	AC	2 ms; 6,940 KB
testcase_28	AC	6 ms; 6,944 KB
testcase_29	AC	11 ms; 6,944 KB
testcase_30	AC	11 ms; 6,940 KB
testcase_31	AC	20 ms; 6,940 KB
testcase_32	AC	9 ms; 6,940 KB
testcase_33	AC	10 ms; 6,944 KB
testcase_34	AC	4 ms; 6,940 KB
testcase_35	AC	4 ms; 6,944 KB
testcase_36	AC	8 ms; 6,940 KB
testcase_37	AC	34 ms; 6,940 KB
testcase_38	AC	54 ms; 6,940 KB
testcase_39	AC	6 ms; 6,940 KB
testcase_40	AC	12 ms; 6,944 KB
testcase_41	AC	7 ms; 6,940 KB
testcase_42	AC	7 ms; 6,944 KB
testcase_43	AC	8 ms; 6,944 KB
testcase_44	AC	10 ms; 6,944 KB
testcase_45	AC	5 ms; 6,944 KB
testcase_46	AC	5 ms; 6,944 KB
testcase_47	AC	9 ms; 6,940 KB
testcase_48	AC	65 ms; 6,944 KB
testcase_49	AC	5 ms; 6,940 KB
testcase_50	AC	5 ms; 6,944 KB
testcase_51	AC	71 ms; 6,940 KB
testcase_52	AC	9 ms; 6,948 KB
testcase_53	AC	4 ms; 6,944 KB
testcase_54	AC	5 ms; 6,944 KB
testcase_55	AC	5 ms; 6,940 KB
testcase_56	AC	4 ms; 6,940 KB
testcase_57	AC	5 ms; 6,944 KB
testcase_58	AC	9 ms; 6,944 KB
testcase_59	AC	6 ms; 6,944 KB
testcase_60	AC	42 ms; 6,940 KB
testcase_61	AC	16 ms; 6,944 KB
testcase_62	AC	2 ms; 6,944 KB
testcase_63	AC	2 ms; 6,948 KB
testcase_64	AC	2 ms; 6,944 KB

ソースコード

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)