VL_2.3B

function [moves, vine] = solver(board, limit)
% LSVG
% MATLAB Contest 2011 ....

moves = [];

n_board = numel(board);
[br bc] = size(board);

if (n_board==0)
    vine = [];
    return;
end

if (n_board==1)
    vine = 1;
    return;
end

[sorted_board, sorted_ii] = sort(board(:),1,'descend');

temp_board = Inf(br+2,bc+2); temp_board(2:(br+1),2:(bc+1)) = board;
d1 = board - temp_board(1:br,2:(bc+1));         
d2 = board - temp_board(2:(br+1),3:(bc+2));     
d3 = board - temp_board(3:(br+2),2:(bc+1));     
d4 = board - temp_board(2:(br+1),1:bc);         

d1(d1 < 0) = Inf;
d2(d2 < 0) = Inf;
d3(d3 < 0) = Inf;
d4(d4 < 0) = Inf;

dd = cat(2,d1(:),d2(:),d3(:),d4(:));
ee = zeros(2*n_board,4);

tv = 0:(n_board-1);
zr = [-1 0 1 0];
zc = [0 1 0 -1];
ee(3*tv+1,:) = dd;
ee(3*tv+2,:) = repmat(zr,n_board,1);
ee(3*tv+3,:) = repmat(zc,n_board,1);
gC = mat2cell(ee',4,3*ones(1,n_board)); 
gC = reshape(gC,br,bc);
gC = cellfun(@sortrows,gC,'UniformOutput',false);
gC = cellfun(@mytrim,gC,'UniformOutput',false);

best_chain = 0;
best_score = 0;

prc_tile = 0.50;
cs1 = cumsum(sorted_board) / sum(board(:));
max_chains = find(cs1>=prc_tile,1,'first');
chains = cell(max_chains,1);

for i1=1:max_chains,
    
    chain_map = zeros(br,bc);
    [curr_rr curr_cc] = ind2sub([br bc],sorted_ii(i1));
    
    this_chain = zeros(n_board,1);
    this_ci = 0;
    
    done = 0;
    while(done==0)

        next_step_ff = 0;
        chain_map(curr_rr,curr_cc) = 1;
        
        this_ci = this_ci + 1;
        this_chain(this_ci) = sub2ind([br bc],curr_rr,curr_cc);
        
        next_step_vv = gC{curr_rr,curr_cc};
        next_step_cc = size(next_step_vv,1);

        for i2=1:next_step_cc,
            
            new_rr = curr_rr + next_step_vv(i2,2);
            new_cc = curr_cc + next_step_vv(i2,3);
            
            if (chain_map(new_rr,new_cc)==0)
                curr_rr = new_rr;
                curr_cc = new_cc;
                next_step_ff = 1;
                break;
            end
            
        end
        
        if (next_step_ff == 0)
            done = 1;
        end
        
    end
    
    this_chain = this_chain(1:this_ci);
    this_chain = this_chain(end:-1:1);
    chains{i1} = this_chain;
    this_score = sum(board(this_chain));
    
    if (this_score > best_score)
        best_score = this_score;
        best_chain = i1;
    end
    
end

vine = chains{best_chain};    


function [zz] = mytrim(vv)
trim_ii = (vv(:,1) == Inf);
zz = vv(~trim_ii,:);