Перейти из форума на сайт.

НовостиФайловые архивы
ПоискАктивные темыТоп лист
ПравилаКто в on-line?
Вход Забыли пароль? Первый раз на этом сайте? Регистрация
Компьютерный форум Ru.Board » Компьютеры » Программы » FAR Manager (часть 6)

Модерирует : gyra, Maz

Maz (26-09-2022 12:52): FAR Manager (часть 7)  Версия для печати • ПодписатьсяДобавить в закладки
На первую страницук этому сообщениюк последнему сообщению

   

Alexyz21



Silver Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Код:
-- Task: обойти конём доску, посещённые ранее клетки и клетки с дырами недоступны
 
local ffi = require("ffi")
local C = ffi.C
ffi.cdef[[
typedef uint8_t t1[9];
]]
 
local F = far.Flags
local board="6x6" -- 8x8 по умолчанию
local holes -- список координат дыр
--holes={{4,4},{4,3}}
--holes={{3,1}}
holes = holes or {}
local ret0 = 0 -- =0 без обязательного возврата в точку старта, =1 с возвратом
--local ret0 = false -- возврат в точку старта
local nm="zc"
local answer = far.InputBox(nil,"Task "..nm,"Enter bx by x0 y0 ret (ex.: "..board..", start 1 1, ret 1: 6 6 1 1 1):",nil,nil,nil,nil,F.FIB_NONE) or ""
local ttime=far.FarClock()
local bx,by,x0,y0,ret0 = string.match(answer,"(%d+)[x, ](%d+)[, ](%d+)[, ](%d+)[, ]([01])")
if not bx then
  ret0,bx,by,x0,y0 = 0,string.match(answer,"(%d+)[x, ](%d+)[, ](%d+)[, ](%d+)")
  if not bx then
    ret0,x0,y0,bx,by,ret = 0,1,1,string.match(answer,"(%d+)[x, ](%d+)")
    if not bx then bx,by = 6,6 end
  end
end
bx,by,x0,y0,ret0 = tonumber(bx),tonumber(by),tonumber(x0),tonumber(y0),tonumber(ret0)==1
local full=bx*by-#holes -- количество клеток для ходов
-- {dx,dy} - вектор хода
--local dx=ffi.new("int8_t[8]",{-1,-2,-2,-1, 1, 2, 2, 1})
--local dy=ffi.new("int8_t[8]",{ 2, 1,-1,-2,-2,-1, 1, 2})
local dx=ffi.new("int8_t[8]",{-1,-1, 2,-2, 1, 1,-2, 2})
local dy=ffi.new("int8_t[8]",{ 2,-2, 1, 1,-2, 2,-1,-1})
-- создаём чистую доску, свободная клетка -1, клетка занятая вектором хода 0-7, дырой 8
local function array(st,...)
  st=st..string.rep('[$]',#{...})
  local array_ct = ffi.typeof(st,...)
  return array_ct({{ -1 }})
end
local t00=array('int8_t' ,bx,by) -- слой векторов с дырами
local t01=array('int16_t',bx,by) -- слой нумерации ходов
for _,v in ipairs(holes) do t00[v[1]-1][v[2]-1]=8 end  -- расставляем дыры 0 based
 
local t1=ffi.new("t1[?]",full) -- дерево оставшихся возможных векторов ходов
bx,by,x0,y0,full = bx-1,by-1,x0-1,y0-1,full-1 -- align from 1 to 0 based
 
local t1s,t1v,x,y -- номер текущего хода, последний (текущий) вектор, координаты текущего поля
local function initt() -- инициализация
  t1s,t1v,x,y = -1,0,x0,y0
end
initt()
 
local cx=ffi.new("int8_t[8]",{-1})
local cy=ffi.new("int8_t[8]",{-1})
local ta=ffi.new("int8_t[8]",{-1})
local ti=ffi.new("int8_t[8]",{-1})
local function around(x,y)
  local tl=-1
  for i=7,0,-1 do
    local x2,y2 = x+dx[i],y+dy[i]
    if x2>=0 and x2<=bx and y2>=0 and y2<=by and t00[x2][y2]<0 then
      tl=tl+1
      local a,v = 0,i<4 and i+4 or i-4 -- противоположный вектор
      for j=7,0,-1 do
        if i==v then goto continue end -- исключаем клетку с которой пришли
        local x3,y3 = x2+dx[j],y2+dy[j]
        if x3>=0 and x3<=bx and y3>=0 and y3<=by and t00[x3][y3]<0 then a=a+1 end
        ::continue::
      end
      ta[tl],ti[tl] = a,i
    end
  end
  -- сортируем по убыванию, обеспечивая приоритет обхода клеток с наименьшим количеством входов
  local l=tl-1
  if l>=0 then
    for j=l,0,-1 do
      local b=true
      for i=l,0,-1 do
        local i1=i+1
        if ta[i]<ta[i1] then
          b,ta[i],ti[i],ta[i1],ti[i1] = false,ta[i1],ti[i1],ta[i],ti[i]
        end
      end
      if b then break end
    end
  end
  return tl
end
 
-- массив клеток на расстоянии 1 хода от старта
local cl=around(x,y)
for i=cl,0,-1 do cx[i],cy[i] = x+dx[ti[i]],y+dy[ti[i]] end
if ret0 then
  t00[cx[0]][cy[0]]=9 -- исключаем клетку финиша из маршрутов  
  full=full-1 -- учитываем недоступность клетки финиша
end
 
--local function chk() for i=cl,0,-1 do if x==cx[i] and y==cy[i] then return true end end return false end -- проверка возврата к старту
local turn,fw = 0,1
local function chk()
  for i=7,0,-1 do
    if x+dx[i]==cx[0] and y+dy[i]==cy[0] then
      t00[cx[0]][cy[0]]=-1
      t01[x][y]=t1s
      t1[t1s][0],t1[t1s][1] = 1,i
      t1s,fw,turn,full = t1s+1,fw+1,turn+1,full+1 -- последний ход
      t01[cx[0]][cy[0]]=t1s
      return true
    end
  end
  return false
end -- проверка возврата к старту
 
local rb,ret,sub = 0,ret0 -- счётчик итераций
while true do
  ::NOD0::
  -- проверяем доступность клеток вокруг
  t1s,turn = t1s+1,turn+1
  t1v=around(x,y)+1
  ffi.copy(t1[t1s]+1,ti,t1v)
  t1[t1s][0]=t1v -- последний вектор хода
  ::NOD1::
  if t1v>0 then local v=t1[t1s][t1v] t00[x][y],t01[x][y] = v,t1s x,y = x+dx[v],y+dy[v] fw=fw+1
  else -- варианты ходов с текущей клетки отсутствуют
    if t1s==full and (not ret or chk()) then if not ret then t01[x][y]=t1s end break end -- последняя клетка?
    ::NOD3::
    repeat -- откат
      t1s=t1s-1 -- удаляем последний неудачный ход
      if t1s<0 then if ret then ret=false initt() goto NOD0 else goto NOD2 end end -- испробованы все пути, решение не найдено
      t1v=t1[t1s][0] -- восстанавливаем индекс последнего вектора
      t00[x][y],t01[x][y] = -1,-1 local v=t1[t1s][t1v] x,y = x-dx[v],y-dy[v] rb=rb+1 -- возвращаемся на ход назад
      t1v=t1v-1 t1[t1s][0]=t1v -- откат на предыдущий вектор хода
    until t1v>0
    if t1s==0 then t00[cx[0]][cy[0]]=-1 local v=t1[t1s][t1v+1] cx[0],cy[0] = x0+dx[v],y0+dy[v] t00[cx[0]][cy[0]]=9 end
    local v=t1[t1s][t1v] t00[x][y],t01[x][y] = v,t1s x,y = x+dx[v],y+dy[v] fw=fw+1
  end
end
::NOD2::
 
bx,by,x0,y0,full = bx+1,by+1,x0+1,y0+1,full+1 -- align from 0 to 1
local s = "Board: "..bx.."x"..by.."\nHoles: "
for i=1,#holes do s=s..holes[i][1]..holes[i][2].."," end
s=string.sub(s,1,-2).."\nSteps: "..(t1s+1).."\nClosed path: "..tostring(ret0).."\n\nSolution: "..(ret==ret0 and "found" or "not found").."\n\nWay: "..x0..y0
local fbx="%0"..#tostring(bx).."d"
local fby="%0"..#tostring(by).."d"
local x2,y2 = x0,y0
for i=0,t1s-1 do x2,y2 = x2+dx[t1[i][t1[i][0]]],y2+dy[t1[i][t1[i][0]]] s=s.." "..string.format(fbx,x2)..string.format(fby,y2) end
s=s.."\n\n"
local bb=bx*by
local sf=#tostring(full)
for y=by,1,-1 do for x=1,bx do local dd=t01[x-1][y-1]+1 s=s..string.format(bb==dd and "*%"..sf.."d*" or " %"..sf.."d ",dd) end s=s.."\n" end
ttime = math.floor((far.FarClock()-ttime)/1000)/1000
s=s.."\n\nIterations: "..(fw+rb).."\n Turnover: "..turn.."\n  Forward: "..fw.."\n Rollback: "..rb.."\n\nTime: "..ttime.." s"
title="Task "..nm..": Chess Knight"
far.Message(s,title)
--local h=io.open([[Z:\temp\1.txt]],"wb") h:write(title.."\n\n"..s) h:close()
 

Всего записей: 3471 | Зарегистр. 16-06-2007 | Отправлено: 18:53 19-07-2021 | Исправлено: Alexyz21, 01:10 20-07-2021
   

На первую страницук этому сообщениюк последнему сообщению

Компьютерный форум Ru.Board » Компьютеры » Программы » FAR Manager (часть 6)
Maz (26-09-2022 12:52): FAR Manager (часть 7)


Реклама на форуме Ru.Board.

Powered by Ikonboard "v2.1.7b" © 2000 Ikonboard.com
Modified by Ru.B0ard
© Ru.B0ard 2000-2024

BitCoin: 1NGG1chHtUvrtEqjeerQCKDMUi6S6CG4iC

Рейтинг.ru