結果

問題 No.1797 永遠のグリッド
ユーザー 👑 obakyan
提出日時 2022-01-01 00:37:43
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 32 ms / 2,000 ms
コード長 4,348 bytes
コンパイル時間 236 ms
コンパイル使用メモリ 6,820 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-09 10:34:02
合計ジャッジ時間 1,341 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

local mfl, mce = math.floor, math.ceil
local bls, brs = bit.lshift, bit.rshift
local bxor = bit.bxor
local bor, band = bit.bor, bit.band

local function grayCode(x)
  return bxor(x, brs(x, 1))
end

-- add_func(idx), rm_func(idx), work_func()
local function grayWalk(size, add_func, rm_func, work_func)
  local prv = 0
  local total = bls(1, size) - 1
  local bpos = {}
  for i = 1, size do
    bpos[bls(1, i - 1)] = i
  end
  -- work_func()
  for i = 1, total do
    local v = grayCode(i)
    if prv < v then
      prv, v = v, v - prv
      add_func(bpos[v])
    else
      prv, v = v, prv - v
      rm_func(bpos[v])
    end
    work_func()
  end
end


local function grayWalk3(size, work_func, box)
  assert(size <= 15)
  local prv = 0
  local total = 3^size - 1
  local rep = 3^(size-1)
  local bpos = {}
  for i = 1, size do
    bpos[bls(1, i - 1)] = i
  end
  local v2 = 0
  for i = 1, size do
    box[i] = 0
  end
  local function incOne()
    if box[1] == 0 then
      box[1] = 1
      v2 = v2 + 1
    elseif box[1] == 1 then
      box[1] = 2
    else
      box[1] = 0
      v2 = v2 - 1
    end
    work_func(1)
  end
  local function incX()
    local z = band(v2, -v2) * 2
    local p = bpos[z]
    if box[p] == 0 then
      box[p] = 1
      v2 = v2 + z
    elseif box[p] == 1 then
      box[p] = 2
    else
      box[p] = 0
      v2 = v2 - z
    end
    work_func(p)
  end
  -- work_func(1)

  incOne()
  incOne()
  for i = 1, rep - 1 do
    incX()
    incOne()
    incOne()
  end
end

local h, w, k = io.read("*n", "*n", "*n")
if k == 1 then print(1) os.exit() end
local n = h * w
local box = {}
if k == 2 then
  local tot = bls(1, n) - 1
  local ret = 0
  local t = {}
  for i = 1, n do box[i] = 0 end
  local function stamp()
    local mul = 1
    local v = 0
    for i = 1, n do
      v = v + mul * box[i]
      mul = mul * 2
    end
    t[v] = true
  end
  for i = 1, tot - 1 do
    if not t[i] then
      ret = ret + 1
      local ti = i
      for j = 1, n do
        box[j] = ti % 2
        ti = brs(ti, 1)
      end
      local tmp = {}
      for rep = 1, h do
        for k = 1, w do
          tmp[k] = box[k]
        end
        for j = 2, h do
          for k = 1, w do
            local idx = (j - 1) * w + k
            box[idx - w] = box[idx]
          end
        end
        for k = 1, w do
          local idx = (h - 1) * w + k
          box[idx] = tmp[k]
        end
        for rep2 = 1, w do
          for k = 1, h do
            tmp[k] = box[(k - 1) * w + 1]
          end
          for k = 2, w do
            for j = 1, h do
              local idx = (j - 1) * w + k
              box[idx - 1] = box[idx]
            end
          end
          for k = 1, h do
            local idx = (k - 1) * w + w
            box[idx] = tmp[k]
          end
          stamp()
        end
      end
    end
  end
  print(ret)
  os.exit()
else
  local tot = 1
  for i = 1, n do tot = tot * 3 end
  tot = tot - 1
  local ret = 0
  local t = {}
  for i = 1, n do box[i] = 0 end
  local function stamp()
    local mul = 1
    local v = 0
    for i = 1, n do
      v = v + mul * box[i]
      mul = mul * 3
    end
    t[v] = true
  end
  for i = 1, tot - 1 do
    local ti = i
    for j = 1, n do
      box[j] = ti % 3
      ti = mfl(ti / 3)
    end
    local c0, c1, c2 = 0, 0, 0
    for j = 1, n do
      if box[j] == 0 then c0 = c0 + 1 end
      if box[j] == 1 then c1 = c1 + 1 end
      if box[j] == 2 then c2 = c2 + 1 end
    end
    if not t[i] and 0 < c0 and 0 < c1 and 0 < c2 then
      ret = ret + 1
      local tmp = {}
      for rep = 1, h do
        for k = 1, w do
          tmp[k] = box[k]
        end
        for j = 2, h do
          for k = 1, w do
            local idx = (j - 1) * w + k
            box[idx - w] = box[idx]
          end
        end
        for k = 1, w do
          local idx = (h - 1) * w + k
          box[idx] = tmp[k]
        end
        for rep2 = 1, w do
          for k = 1, h do
            tmp[k] = box[(k - 1) * w + 1]
          end
          for k = 2, w do
            for j = 1, h do
              local idx = (j - 1) * w + k
              box[idx - 1] = box[idx]
            end
          end
          for k = 1, h do
            local idx = (k - 1) * w + w
            box[idx] = tmp[k]
          end
          stamp()
        end
      end
    end
  end
  print(ret)
  os.exit()
end
0