function moves = solver(mat)
moves = [];
%
%
%
%
%
[n,m] = size(mat);
num_nodes = n*m;
[r,c] = find(zeros(size(mat)) >= 0);
nodes = [(1:num_nodes)', r, c, mat(:), zeros(num_nodes,1)];
segs = [repmat((1:n*m)',2,1), [(1:n*m)'+n; (1:n*m)'+1]];
segs(segs(:,2) > num_nodes,:) = [];segs(mod(segs(:,1),n) == 0 & mod(segs(:,2),n) == 1,:) = [];
segments = [(1:2*num_nodes-n-m)', segs,ones(2*num_nodes-n-m,1),zeros(2*num_nodes-n-m,1)];
for ii = 1:num_nodes
if nodes(ii,4) > 0
addwtto = find(segs(:,1) == ii | segs(:,2) == ii);
segments(addwtto,4) = nodes(ii,4)+segments(addwtto,4);
end
end
[values,repeat] = mmrepeat(sort(mat(:)));
[sortrep,idsortrep] = sort(repeat,'descend');
moves = [];
for i=1:length(idsortrep)
if values(idsortrep(i)) ~=0 && sortrep(i) > 1
[r,c] = find(values(idsortrep(i)) == mat);
distmat = abs(yourDist([r,c],[r,c]',[]));
distmat = tril(distmat);
distmat(distmat == 0) = inf;
tempmoves = [];
for j = 1:size(distmat,1)-1
[dista,nodecon] = min(distmat(:,j));
[newMoves, segments, nodes] = findPath(r(j),c(j),r(nodecon),c(nodecon),nodes,segments,n,m);
if ~isempty(tempmoves)
rows2Remove = zeros(size(tempmoves,1),1);
for ii = 1:size(newMoves,1)
rows2Remove = rows2Remove + all(repmat(newMoves(ii,:),size(tempmoves,1),1) == tempmoves,2);
end
tempmoves(logical(rows2Remove),:) = [];
end
tempmoves = [tempmoves;newMoves];
end
usedNodes = nodes(nodes(:,5) == 2,1);
for iii = 1:size(usedNodes,1)
addwtto = find(segments(:,2) == usedNodes(iii) | segments(:,3) == usedNodes(iii));
segments(addwtto,4) = 25+segments(addwtto,4);
end
nodes(nodes(:,5) == 2,5) = 1;
segments(segments(:,5) == 1,4) = inf;
segsToMod = segments(segments(:,5) == 1,1);
for ii = 1:length(segsToMod)
if segsToMod(ii) <= n*(m-1) % We are horizontal
toAdd = segsToMod(ii)+n;
if ~(toAdd > n*(m-1))
segments(toAdd,4)= inf;
end
toSub = segsToMod(ii)-n;
if ~(toSub <= 0)
segments(toSub,4)= inf;
end
else % vertical
toAdd = segsToMod(ii) - n*(m-1) + 1;
if ~(mod(toAdd,(n-1)) == 1)
segments(toAdd + n*(m-1),4)= inf;
end
toSub = segsToMod(ii) - n*(m-1) - 1;
if ~(mod(toSub,(n-1)) == 0)
segments(toSub + n*(m-1),4)= inf;
end
end
end
segments(:,5) = 0;
moves = [moves;tempmoves];
end
end
function [moves, segments, nodes] = findPath(x1,y1,x2,y2,nodes,segments,n,m)
if (abs(x1-x2) == 1 && abs(y1-y2) == 0) || ...
(abs(x1-x2) == 0 && abs(y1-y2) == 1)
moves = [x2 y2 x1 y1];
% segments((segments(:,2) == sub2ind([n,m],x1,y1) & segments(:,3) == sub2ind([n,m],x2,y2)),4) = ...
% segments((segments(:,2) == sub2ind([n,m],x1,y1) & segments(:,3) == sub2ind([n,m],x2,y2)),4)+1;
segments((segments(:,2) == sub2ind([n,m],x1,y1) & segments(:,3) == sub2ind([n,m],x2,y2)),4) = 0;
segments((segments(:,2) == sub2ind([n,m],x1,y1) & segments(:,3) == sub2ind([n,m],x2,y2)),5) = 1;
return;
else
ind(1) = sub2ind([n,m],x1,y1);
ind(2) = sub2ind([n,m],x2,y2);
for ii = 1:2
addwtto = find(segments(:,2) == ind(ii) | segments(:,3) == ind(ii));
segments(addwtto,4) = -nodes(ind(ii),4)+segments(addwtto,4);
segments(addwtto(segments(addwtto,4)<0),4) = 0;
end
[distance, shortestPath] = dijkstra(nodes,segments,ind(1),ind(2));
for ii = 1:2
addwtto = find(segments(:,2) == ind(ii) | segments(:,3) == ind(ii));
segments(addwtto(segments(addwtto,4)~=0),4) = nodes(ind(ii),4)+segments(addwtto(segments(addwtto,4)~=0),4);
end
if distance > 100000
moves = [];
return;
end
nPath = numel(shortestPath);
moves = zeros(nPath-1,4);
counter = 1;
for ii = 2:nPath
[r1,c1] = ind2sub([n,m],min(shortestPath(ii-1),shortestPath(ii)));
[r2,c2] = ind2sub([n,m],max([shortestPath(ii-1) shortestPath(ii)]));
moves(counter,:) = [r1 c1 r2 c2];
counter = counter+1;
if nodes(shortestPath(ii),5) == 1 && ~nodes(shortestPath(ii),4)
[r,c] = ind2sub([n,m],shortestPath(ii));
moves(counter,:) = [r c r c];
counter = counter+1;
end
nodes(shortestPath(ii),5) = 2;
inds = (segments(:,2) == shortestPath(ii-1) | segments(:,2) == shortestPath(ii)) & ...
(segments(:,3) == shortestPath(ii-1) | segments(:,3) == shortestPath(ii));
% segments(inds,4) = segments(inds,4)+1;
segments(inds,4) = 0;
segments(inds,5) = 1;
end
% viewWeights(segments,nodes);
end
function [y,m]=mmrepeat(x,n)
%MMREPEAT Repeat or Count Repeated Values in a Vector. (MM)
% MMREPEAT(X,N) returns a vector formed from X where X(i) is repeated
% N(i) times. If N is a scalar it is applied to all elements of X.
% N must contain nonnegative integers. N must be a scalar or have the same
% length as X.
%
% For example, MMREPEAT([1 2 3 4],[2 3 1 0]) returns the vector
% [1 1 2 2 2 3] (extra spaces added for clarity)
%
% [X,N]=MMREPEAT(Y) counts the consecutive repeated values in Y returning
% the values in X and the counts in N. Y=MMREPEAT(X,N) and [X,N]=MMREPEAT(Y)
% are inverses of each other if N contains no zeros and X contains unique
% elements.
%
% See also MMSUBDIV.
% D.C. Hanselman, University of Maine, Orono, ME 04469
% 3/2/99, 4/14/99
% Mastering MATLAB 6, Prentice Hall, ISBN 0-13-019468-9
if nargin==2 % MMREPEAT(X,N)
xlen=length(x);
nlen=length(n);
if ndims(x)~=2 | prod(size(x))~=xlen
;
else
[r,c]=size(x);
end
x=reshape(x,1,xlen); % make x a row vector
if nlen==1 % scalar n case, repeat all elements the same amount
if n<=0 % quick exit for special case
y=[];
return
end
y=x(ones(1,n),:); % duplicate x to make n rows each containing x
y=y(:); % stack each column into a single column
if r==1 % input was a row so return a row
y=y.';
end
else % vector n case
iz=find(n>0); % look at positive repeats only
x=x(iz);
n=n(iz);
csn=cumsum(n);
y=zeros(1,csn(end)); % preallocate temp/output variable
y(csn(1:end-1)+1)=1; % mark indices where values increment
y(1)=1; % poke in first index
y=x(cumsum(y)); % use cumsum to set indices
if c==1 % input was a column so return a column
y=y.';
end
end
elseif nargin==1 % MMREPEAT(Y)
xlen=length(x);
if ndims(x)~=2 | prod(size(x))~=xlen
;
else
[r,c]=size(x);
end
x=reshape(x,1,xlen); % make x a row vector
xnan=isnan(x);
xinf=isinf(x);
if any(xnan|xinf) % handle case with exceptions
ntmp=sum(rand(1,4))*sqrt(realmax); % replacement for nan's
itmp=1/ntmp; % replacement for inf's
x(xnan)=ntmp;
x(xinf)=itmp.*sign(x(xinf));
y=[1 diff(x)]~=0; % places where distinct values begin
m=diff([find(y) xlen+1]); % counts
x(xnan)=nan; % poke nan's and inf's back in
x(xinf)=inf*x(xinf);
else % x contains only algebraic numbers
y=[1 diff(x)]~=0; % places where distinct values begin
m=diff([find(y) xlen+1]); % counts
end
y=x(y); % the unique values
if c==1
y=y.';
m=m.';
end
end
function [dist,path] = dijkstra(nodes,segments,start_id,finish_id)
%DIJKSTRA Calculates the shortest distance and path between points on a map
% using Dijkstra's Shortest Path Algorithm
%
% [DIST, PATH] = DIJKSTRA(NODES, SEGMENTS, SID, FID)
% Calculates the shortest distance and path between start and finish nodes SID and FID
%
% [DIST, PATH] = DIJKSTRA(NODES, SEGMENTS, SID)
% Calculates the shortest distances and paths from the starting node SID to all
% other nodes in the map
%
% Note:
% DIJKSTRA is set up so that an example is created if no inputs are provided,
% but ignores the example and just processes the inputs if they are given.
%
% Inputs:
% NODES should be an Nx3 or Nx4 matrix with the format [ID X Y] or [ID X Y Z]
% where ID is an integer, and X, Y, Z are cartesian position coordinates)
% SEGMENTS should be an Mx3 matrix with the format [ID N1 N2]
% where ID is an integer, and N1, N2 correspond to node IDs from NODES list
% such that there is an [undirected] edge/segment between node N1 and node N2
% SID should be an integer in the node ID list corresponding with the starting node
% FID (optional) should be an integer in the node ID list corresponding with the finish
%
% Outputs:
% DIST is the shortest Euclidean distance
% If FID was specified, DIST will be a 1x1 double representing the shortest
% Euclidean distance between SID and FID along the map segments. DIST will have
% a value of INF if there are no segments connecting SID and FID.
% If FID was not specified, DIST will be a 1xN vector representing the shortest
% Euclidean distance between SID and all other nodes on the map. DIST will have
% a value of INF for any nodes that cannot be reached along segments of the map.
% PATH is a list of nodes containing the shortest route
% If FID was specified, PATH will be a 1xP vector of node IDs from SID to FID.
% NAN will be returned if there are no segments connecting SID to FID.
% If FID was not specified, PATH will be a 1xN cell of vectors representing the
% shortest route from SID to all other nodes on the map. PATH will have a value
% of NAN for any nodes that cannot be reached along the segments of the map.
%
% Example:
% dijkstra; % calculates shortest path and distance between two nodes
% % on a map of randomly generated nodes and segments
%
% Example:
% nodes = [(1:10); 100*rand(2,10)]';
% segments = [(1:17); floor(1:0.5:9); ceil(2:0.5:10)]';
% figure; plot(nodes(:,2), nodes(:,3),'k.');
% hold on;
% for s = 1:17
% if (s <= 10) text(nodes(s,2),nodes(s,3),[' ' num2str(s)]); end
% plot(nodes(segments(s,2:3)',2),nodes(segments(s,2:3)',3),'k');
% end
% [d, p] = dijkstra(nodes, segments, 1, 10)
% for n = 2:length(p)
% plot(nodes(p(n-1:n),2),nodes(p(n-1:n),3),'r-.','linewidth',2);
% end
% hold off;
%
% Author: Joseph Kirk
% Email: jdkirk630 at gmail dot com
% Release: 1.3
% Release Date: 5/18/07
% MAIN FUNCTION - DIJKSTRA'S ALGORITHM
% initializations
node_ids = nodes(:,1);
[num_map_pts,cols] = size(nodes);
table = sparse(num_map_pts,2);
shortest_distance = Inf(num_map_pts,1);
settled = zeros(num_map_pts,1);
path = num2cell(NaN(num_map_pts,1));
col = 2;
pidx = find(start_id == node_ids);
shortest_distance(pidx) = 0;
table(pidx,col) = 0;
settled(pidx) = 1;
path(pidx) = {start_id};
if (nargin < 4) % compute shortest path for all nodes
while_cmd = 'sum(~settled) > 0';
else % terminate algorithm early
while_cmd = 'settled(zz) == 0';
zz = find(finish_id == node_ids);
end
while eval(while_cmd)
% update the table
table(:,col-1) = table(:,col);
table(pidx,col) = 0;
% find neighboring nodes in the segments list
neighbor_ids = [segments(node_ids(pidx) == segments(:,2),3);
segments(node_ids(pidx) == segments(:,3),2)];
neighbour_weights = [segments(node_ids(pidx) == segments(:,2),4);
segments(node_ids(pidx) == segments(:,3),4)];
% calculate the distances to the neighboring nodes and keep track of the paths
for k = 1:length(neighbor_ids)
cidx = find(neighbor_ids(k) == node_ids);
if ~settled(cidx)
% d1 = sum(abs((nodes(pidx,2:cols) - nodes(cidx,2:cols))));
if nodes(cidx,4) >0 && cidx ~= start_id && cidx ~= finish_id && ...
nodes(start_id,4) ~= nodes(cidx,4)
% d = inf;
continue;
else
d = neighbour_weights(k)+1e-5;
if isinf(d)
continue;
end
end
if (table(cidx,col-1) == 0) || ...
(table(cidx,col-1) > (table(pidx,col-1) + d))
table(cidx,col) = table(pidx,col-1) + d;
tmp_path = path(pidx);
path(cidx) = {[tmp_path{1} neighbor_ids(k)]};
else
table(cidx,col) = table(cidx,col-1);
end
end
end
% find the minimum non-zero value in the table and save it
nidx = find(table(:,col));
ndx = find(table(nidx,col) == min(table(nidx,col)));
if isempty(ndx)
break
else
pidx = nidx(ndx(1));
shortest_distance(pidx) = table(pidx,col);
settled(pidx) = 1;
end
end
if (nargin < 4) % return the distance and path arrays for all of the nodes
dist = shortest_distance';
path = path';
else % return the distance and path for the ending node
dist = shortest_distance(zz);
path = path(zz);
path = path{1};
end
function z = yourDist(w,p,fp)
[S,R] = size(w);
[R2,Q] = size(p);
z = zeros(S,Q);
if (Q<S)
p = p';
copies = zeros(1,S);
for q=1:Q
z(:,q) = sum(abs(w-p(q+copies,:)),2);
end
else
w = w';
copies = zeros(1,Q);
for i=1:S
z(i,:) = sum(abs(w(:,i+copies)-p),1);
end
end
|
