function out=dtw(template,test)
% template=[0 0 0;5 4 1;4 3 2;3 2 1]';
% test=[0 0 0;5 3 1;4 3 2;4 3 2;3 3 1]';
% template=liu1;
% test=MelMatix;
test=fliplr(test);
match=ones(size(test,2),size(template,2));
MatchRuler=path_restrict(match);
Distance=zeros(size(test,2),size(template,2));

Square=((size(test,2)+size(template,2))-abs(size(test,2)-size(template,2)))/2;
b=size(template,2);a=size(test,2);
Distance(a-1,2)=sum(abs(template(:,2)-test(:,a-1)));
for S=2:Square-1
    for i=2:S
        if(MatchRuler(a-S,i)>0)
            if(MatchRuler(a-S+1,i)>0) c1=sum(abs(template(:,i)-test(:,a-S)))+Distance(a-S+1,i);else c1=[ ];end
            if(MatchRuler(a-S+1,i-1)>0) c2=sum(abs(template(:,i)-test(:,a-S)))+Distance(a-S+1,i-1);else c2=[ ];end
            if(MatchRuler(a-S,i-1)>0) c3=sum(abs(template(:,i)-test(:,a-S)))+Distance(a-S,i-1);else c3=[ ];end
            c=[c1,c2,c3];
            Distance(a-S,i)=min(c);
        end
        if(MatchRuler(a-i+1,S+1)>0)
            if(MatchRuler(a-i+2,S+1)>0) c1=sum(abs(template(:,S+1)-test(:,a-i+1)))+Distance(a-i+2,S+1);else c1=[ ];end
            if(MatchRuler(a-i+2,S)>0) c2=sum(abs(template(:,S+1)-test(:,a-i+1)))+Distance(a-i+2,S);else c2=[ ];end
            if(MatchRuler(a-i+1,S)>0) c3=sum(abs(template(:,S+1)-test(:,a-i+1)))+Distance(a-i+1,S);else c3=[ ];end
            c=[c1,c2,c3];
            Distance(a-i+1,S+1)=min(c);
        end
    end
     if(MatchRuler(a-S,S+1)>0)
            if(MatchRuler(a-S+1,S+1)>0) c1=sum(abs(template(:,S+1)-test(:,a-S)))+Distance(a-S+1,S+1);else c1=[ ];end
            if(MatchRuler(a-S+1,S)>0) c2=sum(abs(template(:,S+1)-test(:,a-S)))+Distance(a-S+1,S);else c2=[ ];end
            if(MatchRuler(a-S,S)>0) c3=sum(abs(template(:,S+1)-test(:,a-S)))+Distance(a-S,S);else c3=[ ];end
            c=[c1,c2,c3];
            Distance(a-S,S+1)=min(c);
    end
end
if(a>b)
    for i=a-b:-1:1
        for j=2:b
            if(MatchRuler(i,j)>0)
                if(MatchRuler(i+1,j)>0) c1=sum(abs(template(:,j)-test(:,i)))+Distance(i+1,j);else c1=[ ];end
                if(MatchRuler(i+1,j-1)>0) c2=sum(abs(template(:,j)-test(:,i)))+Distance(i+1,j-1);else c2=[ ];end
                if(MatchRuler(i,j-1)>0) c3=sum(abs(template(:,j)-test(:,i)))+Distance(i,j-1);else c3=[ ];end
                c=[c1,c2,c3];
                Distance(i,j)=min(c);
            end
        end
    end
end
if(a<b)
    for j=a+1:b
        for i=a-1:-1:1
            if(MatchRuler(i,j)>0)
                if(MatchRuler(i+1,j)>0) c1=sum(abs(template(:,j)-test(:,i)))+Distance(i+1,j);else c1=[ ];end
                if(MatchRuler(i+1,j-1)>0) c2=sum(abs(template(:,j)-test(:,i)))+Distance(i+1,j-1);else c2=[ ];end
                if(MatchRuler(i,j-1)>0) c3=sum(abs(template(:,j)-test(:,i)))+Distance(i,j-1);else c3=[ ];end
                c=[c1,c2,c3];
                Distance(i,j)=min(c);
            end
        end
    end
end
out=Distance(1,b);