grade(map,n,d);

function score = grade(map,n,d);
%GRADE Make sure the answer is valid and compute its score.
%
% Copyright 2004 The MathWorks, Inc.

% Make sure the answer is well-formed.
if (size(d,1)~=size(map,1) | size(d,2)~=size(map,2))
   error('The returned matrix has the wrong dimension');
end
if (length(unique(d)) ~= n)
   error('All precincts must be represented.');
end
if (any(unique(d)' ~= 1:n))
   error('The returned matrix values must be between 1 and the number of precincts.');
end

% Check for contiguous regions and compute score.
total = sum(map(:));
goal = total/n;
misplacedPeople = 0;
for i = 1:n
   if ~isContiguous(d==i)
      error('All members in a precinct must be contiguous.');
   end
   % Score it
   misplacedPeople = misplacedPeople + abs(goal - sum(map(d==i)));
end
% Calculate the percent displaced.  Divide by two since each person is counted
% twice: once for being to many in one and once for being too few in another.
score = 100*misplacedPeople/2/total;

%===============================================================================
function tf = isContiguous(a)
% Returns true if at least one of the elements is true and is four-connected to
% all other true elements.

% This allocates iList and jList so we won't have to grow the stack.  It also
% populates the first position, but we will overwrite the rest.
[iList,jList] = find(a);

% All false.  Bail out.
if isempty(iList)
   tf = false;
   return
end

% Start walking recursively from the first.  Don't stop until reaching all
% connected positions.
index = 1;
while (index ~= 0)
   r = iList(index);
   c = jList(index);
   index = index-1;
   a(r,c) = 0;
   if (r > 1) & a(r-1,c)
      index = index+1;
      iList(index) = r-1;
      jList(index) = c;
   end
   if (r < size(a,1)) & a(r+1,c)
      index = index+1;
      iList(index) = r+1;
      jList(index) = c;
   end
   if (c > 1) & a(r,c-1)
      index = index+1;
      iList(index) = r;
      jList(index) = c-1;
   end
   if (c < size(a,2)) & a(r,c+1)
      index = index+1;
      iList(index) = r;
      jList(index) = c+1;
   end
end

% If there are any we didn't get to, it wasn't contiguous.
tf = ~any(a(:));