Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # 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)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement