# LAVIRINT
# K4, 1. SAMO GRAF(trazi sve putanje preko dfsa),2. primena svega toga u lavirintu(prebrojavanje, obicna pretraga sa bfsa)
# get path, u jednom od ta dva
# 1x5, prva vrsta
# zelena polja su zidovi, zanemarujemo prilikom pretrage
# BFS je nakraca pretraga
# kovceg sa blagom i rupe
# matricu susedstva sami pisemo
# pozive isto sami kucamo
# prvo includujemo skripte (ne napamet), 3 skripte (sablon, uslov, poziv), definisemo velicinu lavirinta
# generisemo graf metodom (emptyLabyrinth), nakon toga definisemo tipova polja(max 4, zavisi koliko tipova imamo),
# poziv koda, BFS, DFS, get path(ako se trazi), onda ispisujemo lavirint

#lavirint pr 8.1
mutable struct Cvor
    color::Char
    type::Char
    d::Int
    pred::Int
end
mutable struct labyrinth
   rows::Int64
   cols::Int64
   AdjMatrix::Array{Int, 2}
   V::Array{Cvor, 1}
end

function generateTableAdjMatrix(nbRows, nbColumns)
    adjMatrix = zeros(nbRows*nbColumns, nbRows*nbColumns);
    adjMatrixRowCounter = 0;

    for i = 1:nbRows
       for j = 1:nbColumns
           currentId = (i-1)*nbColumns + j;
           neighbourRow = [currentId-1 currentId currentId+1];
           neighbourMatrix = [neighbourRow .- nbColumns; neighbourRow; neighbourRow .+ nbColumns];

           startRowIndex = 1;
           startColumnIndex = 1;
           endRowIndex = 3;
           endColumnIndex = 3;

           if i == 1
               startRowIndex = 2;
           end
           if j == 1
               startColumnIndex = 2;
           end
           if i == nbRows
              endRowIndex = 2;
           end
           if j == nbColumns
              endColumnIndex = 2;
           end

       neighbours = [];
           for m = startRowIndex:endRowIndex
              for n = startColumnIndex:endColumnIndex
                  if neighbourMatrix[m,n]!=currentId
                    push!(neighbours, neighbourMatrix[m,n]);
                  end
              end
           end

           adjRow = zeros(1, nbRows*nbColumns);
           for m = 1:length(neighbours)
                adjRow[neighbours[m]] = 1;
           end

           adjMatrixRowCounter  = adjMatrixRowCounter + 1;
           adjMatrix[adjMatrixRowCounter, :] = adjRow;
       end
    end
    return adjMatrix
end

function emptyLabyrinth(nrow, ncol)
   AdjMatrix = generateTableAdjMatrix(nrow, ncol)
   V = Array{Cvor}(undef, nrow*ncol)
   for i in 1:nrow*ncol
     V[i] = Cvor('W', '*', 0, 0)
   end
   return labyrinth(nrow, ncol, AdjMatrix, V)
end

function printLabyrinthType(G)
  for i in 1:G.rows
    for j in 1:G.cols
      print(" $(G.V[(i-1)*G.cols+j].type)")
    end
  println()
  end
end

function printLabyrinthColor(G)
  for i in 1:G.rows
    for j in 1:G.cols
      print(" $(G.V[(i-1)*G.cols+j].color)")
    end
  println()
  end
end

function defineNodesType!(G, nodes, type )
    for u = nodes
        G.V[u].type = type;
    end
end

function printLabyrinthPath(G, path)
  for i in 1:G.rows
    for j in 1:G.cols
       if ((i-1)*G.cols+j) in path
         print(" *")
       else
         print(" $(G.V[(i-1)*G.cols+j].type)")
       end
    end
  println()
  end
end

#BFS
function BFS!(G, s)
    v = 1:size(G.AdjMatrix, 1)
    for u in v
    if u != s
    G.V[u].color = 'W'
    G.V[u].d = typemax(Int)
    G.V[u].pred = -1
    end
    end
    G.V[s].color = 'G' #gray
    G.V[s].d = 0
    G.V[s].pred = -1
    Q = Int[]
    push!(Q, s)

    while ~isempty(Q)
        u = Q[1]
        deleteat!(Q, 1)
        for v in findall(G.AdjMatrix[u,:].==1)
        if G.V[v].color=='W' &&
        G.V[v].type == 'P'
        G.V[v].color = 'G'
        G.V[v].d = G.V[u].d + 1
        G.V[v].pred = u
        push!(Q, v)
        end
        end
        G.V[u].color = 'B'
    end
end

function getPath(G, idStart, idEnd)
    path = Int[]
    temp = idEnd;
    while (temp != idStart)
    path = [temp; path]
    temp = G.V[temp].pred;
    end
    return [idStart; path]
end

# primer81.jl
# inicjalizujemo podatke u grafu

nbRows = 5;
nbColumns = 5;
G = emptyLabyrinth(nbRows, nbColumns)

defineNodesType!(G,[1 2 3 5 6 8 10 11 12 13 14 15 17 21 22 23 24 25],'P'); #PUT
defineNodesType!(G, [4 7 9 16 18 19 20], 'Z'); #ZID

println("Izgled lavirinta pre obilaska")
println()
printLabyrinthType(G)
println()
println("Ispis lavirinta pre obilaska")
println()
printLabyrinthColor(G)
println()

println("Ispis lavirinta posle obilaska")
println()
BFS!(G, 21);
printLabyrinthColor(G)
println()

println("Izgled lavirinta sa putanjom")
println()
path = getPath(G, 21, 5)
printLabyrinthPath(G, path)
println()

# pr 8.2

function BFS2!(G, s)    # sablonski deo
    v = 1:size(G.AdjMatrix, 1)
    for u in v
    if u != s
    G.V[u].color = 'W'
    G.V[u].d = typemax(Int)
    G.V[u].pred = -1
    end
end
    G.V[s].color = 'G'
    G.V[s].d = 0
    G.V[s].pred = -1
    Q = Int[]
    push!(Q, s)

    while ~isempty(Q)
        u = Q[1]
        deleteat!(Q, 1)
        if G.V[u].type == 'C'   # odavde krece ne sablonski deo
        path = Int[]
        temp = u;
        while (temp != s)
        path = [temp; path]
        temp = G.V[temp].pred;
        end
        return [s; path]
        else
        for v in findall(G.AdjMatrix[u,:].==1)
        if G.V[v].color=='W' && G.V[v].type!='Z'
        G.V[v].color = 'G'
        G.V[v].d = G.V[u].d + 1
        G.V[v].pred = u
        push!(Q, v)
        end
        end
        end
        G.V[u].color = 'B'
    end
        return Int[];
end

nbRows = 8;
nbColumns = 8;
# generisanje lavirinta
G = emptyLabyrinth(nbRows, nbColumns)
# definisanje tipa za odredjeni podskup cvorova iz grafa
defineNodesType!(G, 1:nbRows*nbColumns, 'P');
defineNodesType!(G, [5 9 10 11 13 15 21 23 24 26 28 29 31 34 44 45 46 47 50 55
58 60 61 63], 'Z');
defineNodesType!(G, [62], 'C');
path = BFS2(G, 57)
# ispis lavirinta
println("Ispis putanje i izgled lavirinta posle obilaska")
println("PATH = $path")
printLabyrinthPath(G, path)

# pazi kako indeksiras, ide ovako
# 1 2 3 4 5 6 7 8
# 9 10 11 12 13 14 15 16
# 17 .... za 8x8


# zadatak 8.1

#DFS
function DFS(G, u, k)
    v = 1:size(G.AdjMatrix, 1);
    for u = v
    G.V[u].color = 'W';
    G.V[u].pred = -1;
    end
    for u = v
        if G.V[u].color == 'W';
            return DFS_Visit!(G, u, k);
    end
    end
end
    function DFS_Visit!(G, u, k)
        path =[]
        if u == k
            path=[u]
            return path
        G.V[u].color = 'G';
        for v in findall(G.AdjMatrix[u,:].==1)
        if G.V[v].color=='W' && G.V[v].type != 'Z'
        G.V[v].pred = u;
        path = DFS_Visit!(G, v, k);
        if length(path) != 0
            return [u, path]
        end
        end
        G.V[u].color = 'B';
        return path
    end
#
function getPath(G, idStart, idEnd)
    path = Int[]
    temp = idEnd;
    while (temp != idStart)
    path = [temp; path]
    temp = G.V[temp].pred;
    end
    return [idStart; path]
end



nbRows = 8;
nbColumns = 8;
# generisanje lavirinta
G = emptyLabyrinth(nbRows, nbColumns)
# definisanje tipa za odredjeni podskup cvorova iz grafa
defineNodesType!(G, 1:nbRows*nbColumns, 'P');
defineNodesType!(G, [5 9 10 11 13 15 21 23 24 26 28 29 31 34 44 45 46 47 50 55 58 60 61 63], 'Z');
defineNodesType!(G, [62], 'C');
path = DFS(G, 57)
# ispis lavirinta
println("Ispis putanje i izgled lavirinta posle obilaska")
println("PATH = $path")
printLabyrinthPath(G, path)