os.execute"cls"
local arg = {...}

local function split(str)
    local t = {}
    for match in str:gmatch(".") do
        t[#t+1] = match
    end
    return t
end

local function replace(str,what,with)
    return string.gsub(str,what,with)
end

local function loadFile(path)
    local f = assert(io.open(path,"r"))
    local content = f:read("*all")
    f:close()
    return content
end

local function parseLevel(raw)
    local height, width = raw:match("([0-9]+) ([0-9]+)")
    local off = #height + #width + 2

    raw = split(raw:sub(off))

    local level = {}
    local curLevel

    for i = 1,#raw do
        local current = raw[i]
        if((i-1)%width==0) then
            level[#level+1] = {}
            curLevel = level[#level]
        end
        curLevel[#curLevel+1] = current
    end
    return level
end

local function getRelatives(level,x1,y1)
    local relatives = {}
    if(y1-1~=0) then
        table.insert(relatives,{
            x=x1,
            y=y1-1,
            orientation="N"
            })
    end
    if(x1+1<=#level[1]) then
        table.insert(relatives,{
            x=x1+1,
            y=y1,
            orientation="O"
            })
    end
    if(y1+1<=#level) then
        table.insert(relatives,{
            x=x1,
            y=y1+1,
            orientation="S"
            })
    end
    if(x1-1~=0) then
        table.insert(relatives,{
            x=x1-1,
            y=y1,
            orientation="W"
            })
    end
    return relatives
end

local function findKassiopeia(level)
    for y = 1,#level do
        for x = 1,#level[1] do
            if(level[y][x]=="K") then
                return x,y
            end
        end
    end
end

local function getWhitespaces(level)
    local i = 0
    for y = 1,#level do
        for x = 1,#level[1] do
            if(level[y][x] == " ") then
                i = i+1
            end
        end
    end
    return i+1
end

local marked = {}
local found = 0

local function canReachEveryField(level,startX,startY)
    if(level[startY][startX]=="#") then
        return
    elseif(marked[startX.." "..startY]) then
        return
    else --Alles was nicht markiert ist, und auch nicht # ist, muss ein begehbares feld sein.
        marked[startX.." "..startY] = true
        found = found+1
    end
    local relatives = getRelatives(level,startX,startY)
    for k,v in pairs(relatives) do
        canReachEveryField(level,v.x,v.y)
    end
end

local finalString = {}

local function tCopy(t)
    local tt = {}
    for k,v in pairs(t) do
        tt[k] = v
    end
    return tt
end

local function realSize(t)
    local i = 0
    for k,v in pairs(t) do
        i = i+1
    end
    return i
end

local function contains(t,what)
    for k,v in pairs(t) do
        if(v==what) then return true end
    end
    return false
end

local function onlyOnce(t)
    local tt = {}
    for k,v in pairs(t) do
        if(not contains(tt,v)) then
            table.insert(tt,v)
        end
    end
    return tt
end

local function searchPath(level,posX,posY,marked,curStr,orientation)
    local marked = marked or {}
    local curStr = curStr or ""

    if(realSize(marked)==getWhitespaces(level)) then
        table.insert(finalString,curStr)
    end

    if(level[posY][posX]=="#") then
        return
    end

    if(marked[posX.." "..posY]) then
        return
    end

    marked[posX.." "..posY] = true
    if(orientation) then
        curStr = curStr..orientation
    end


    local relatives = getRelatives(level,posX,posY)

    for k,v in pairs(relatives) do
        searchPath(level,v.x,v.y,tCopy(marked),curStr,v.orientation)
    end

    if(#marked==getWhitespaces(level)) then
        table.insert(finalString,curStr)
    end

end

--Ist nur zum debuggen. Hat keinen wirklichen nutzen.
local function printLevel(level)
    for k,v in pairs(level) do
        print(table.concat(v,""))
    end
end



--Das muss man nicht machen, aber so finde ich das ein wenig ordentlicher.
local function main()
    local rawData = loadFile(arg[1] and arg[1] or "currentLevel.txt")
    print(rawData)
    rawData = replace(rawData,"\n","")
    rawData = replace(rawData,"\r","")
    local level = parseLevel(rawData)
    local startX,startY = findKassiopeia(level)
    searchPath(level,startX,startY)
    local paths = onlyOnce(finalString)
    if(#paths==0) then print("Es gibt keinen Weg.") return end
    print("Es wurden "..#paths.." Wege gefunden.")
    for k,v in pairs(paths) do
        print(k,v)
    end
end

main()