結果

問題 No.1668 Grayscale
コンテスト
ユーザー obakyan
提出日時 2021-09-12 21:48:13
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 1,745 ms / 4,000 ms
コード長 1,407 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 307 ms
コンパイル使用メモリ 6,944 KB
実行使用メモリ 145,280 KB
最終ジャッジ日時 2024-06-24 17:11:31
合計ジャッジ時間 7,182 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

local mfl, mce = math.floor, math.ceil
local mmi, mma = math.min, math.max
local h, w, cn = io.read("*n", "*n", "*n")
local n = h * w
local t = {}
local cmap = {}
local cuniq = {}
for i = 1, h do
  for j = 1, w do
    local col = io.read("*n")
    t[(i - 1) * w + j] = col
    cmap[col] = true
  end
end
for k, v in pairs(cmap) do table.insert(cuniq, k) end
table.sort(cuniq)
cn = #cuniq
for i = 1, cn do
  cmap[cuniq[i]] = i
end

for i = 1, n do
  t[i] = cmap[t[i]]
end

local cpos = {}
for i = 1, cn do
  cpos[i] = {}
end
for i = 1, n do
  table.insert(cpos[t[i]], i)
end
local ret = {}
for i = 1, n do ret[i] = -1 end
for i = 1, #cpos[1] do
  ret[cpos[1][i]] = 1
end
for i = 2, cn do
  local v = ret[cpos[i - 1][1]]
  for j = 1, #cpos[i] do
    local pos = cpos[i][j]
    local row = mce(pos / w)
    local col = pos - (row - 1) * w
    if 1 < row and t[pos - w] < t[pos] then
      v = mma(v, 1 + ret[pos - w])
    end
    if row < h and t[pos + w] < t[pos] then
      v = mma(v, 1 + ret[pos + w])
    end
    if 1 < col and t[pos - 1] < t[pos] then
      v = mma(v, 1 + ret[pos - 1])
    end
    if col < w and t[pos + 1] < t[pos] then
      v = mma(v, 1 + ret[pos + 1])
    end
  end
  for j = 1, #cpos[i] do
    ret[cpos[i][j]] = v
  end
end
-- for i = 1, h do
  -- for j = 1, w do
    -- io.write(ret[(i - 1) * w + j])
    -- io.write(j == w and "\n" or " ")
  -- end
-- end
print(ret[cpos[cn][1]])
0