Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- fid=fopen('input.txt');
- x=[];
- while 1
- tline = fgetl(fid);
- if ~ischar(tline), break, end
- x = [x;double(tline)-48];
- end
- fclose(fid);
- x1 = x+1; x1(x1>9)=1;
- x2 = x1+1; x2(x2>9)=1;
- x3 = x2+1; x3(x3>9)=1;
- x4 = x3+1; x4(x4>9)=1;
- x5 = x4+1; x5(x5>9)=1;
- x6 = x5+1; x6(x6>9)=1;
- x7 = x6+1; x7(x7>9)=1;
- x8 = x7+1; x8(x8>9)=1;
- x = [x,x1,x2,x3,x4;
- x1,x2,x3,x4,x5;
- x2,x3,x4,x5,x6;
- x3,x4,x5,x6,x7;
- x4,x5,x6,x7,x8];
- L = size(x,1);
- startIdx = 1;
- goalIdx = L*L;
- openSet = startIdx;
- cameFrom = [];
- gScore = inf(L);
- gScore(startIdx) = 0;
- fScore = inf(L);
- fScore(startIdx) = (L-1)+(L-1); % Manhattan distance from start to finish
- while ~isempty(openSet)
- [~,idx] = min(fScore(openSet));
- current = openSet(idx);
- if current==goalIdx
- disp('path complete')
- break
- end
- openSet(openSet == current) = [];
- [r,c] = ind2sub(size(x),current);
- r1 = r-1; c1 = c;
- r2 = r+1; c2 = c;
- r3 = r; c3 = c-1;
- r4 = r; c4 = c+1;
- neighbours = [];
- if r1>0
- neighbours = [neighbours,sub2ind(size(x),r1,c1)];
- end
- if r2<(L+1)
- neighbours = [neighbours,sub2ind(size(x),r2,c2)];
- end
- if c3>0
- neighbours = [neighbours,sub2ind(size(x),r3,c3)];
- end
- if c4<(L+1)
- neighbours = [neighbours,sub2ind(size(x),r4,c4)];
- end
- for i=1:size(neighbours,2)
- tentative_gScore = gScore(current) + x(neighbours(i));
- if tentative_gScore < gScore(neighbours(i))
- [rn,cn] = ind2sub(size(x),neighbours(i));
- cameFrom(rn,cn) = current;
- gScore(rn,cn) = tentative_gScore;
- h = (L-rn)+(L-cn);
- fScore(rn,cn) = tentative_gScore + h;
- if ~any(neighbours(i)==openSet)
- openSet = [openSet,neighbours(i)];
- end
- end
- end
- end
- disp(fScore(end));
Advertisement
Add Comment
Please, Sign In to add comment