[教學] Programming 8: "The Blacksheep Story Part II"

題目網址

題目大意：

給定一地圖，由起點出發，將地圖上所有星號走過一遍，再到終點。

星號上有兩個數值，分別為撿起來時的cost，與之後每一步增加的cost，啟始cost為1。

要求cost最少的路線。

ex. 如下圖，由START開始，往下走兩格(cost 2)，撿起星號(cost 3)，再往右走兩格(cost 10，因每步cost由1增加成5)，撿起星號(cost 7)，最後往上走兩格到END(cost (1+4+8)*2 = 26)。總共cost為48，是最佳解。



解法：

由於不限時間，直接使用暴力破解。

將圖上的點作順序排列(permutation)，並一一嘗試所花費的cost，取出最小值。

以下程式以 Ruby 執行：

# Author      : mashimaro
# Last Modify : 2008/01/27

$MAP = [
'0000000000000000E0',
'011111111111111111',
'000000000000F01000',
'00010000000010101H',
'000100000000001011',
'0I0100010000101000',
'000100010000001001',
'00010001000101001A',
'000000010001s0010e',
'000100010000111000',
'000100000000010000',
'00010100C000100000',
'000001000001000000',
'000001110010000000',
'000100000100010001',
'0111000010001D1G1B',
'00J101100101000100',
'000100000000000000'
];

$COST = [1, 2, 3, 7, 7, 8, 9, 9, 19, 97];

def calculate_path_len(arrDouble, x, y, val)
if($MAP[x][y].chr != '1' && arrDouble[x][y] > val)
  arrDouble[x][y] = val;
  #up
  arrDouble = calculate_path_len(arrDouble, x - 1, y, val + 1) if(x > 0);
  #down
  arrDouble = calculate_path_len(arrDouble, x + 1, y, val + 1) if(x < 17);
  #left
  arrDouble = calculate_path_len(arrDouble, x, y - 1, val + 1) if(y > 0);
  #right
  arrDouble = calculate_path_len(arrDouble, x, y + 1, val + 1) if(y < 17);
end
#if($MAP[x][y])
#puts $MAP;
arrDouble;
end


pathArray = Array.new(11){Array.new(12)};

i = 0;

for s in ['s', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
j = 0;
$MAP.each { |str|
if(str.index(s))
  #puts str + ' ' + str.index(s).to_s;
  arrDouble = Array.new(18){Array.new(18, 99)};
  arrDouble = calculate_path_len(arrDouble, j, str.index(s), 0);

  #output arrDouble
  if(1 == 0)
   x = 0;
   while(x < 18)
    y = 0;
    while(y < 18)
     print arrDouble[x][y].to_s + ' ';
     y = y + 1;
    end
    puts ;
    x = x + 1;
   end
 end

 #calculate pathArray
 m = 0;
 for tmp_s in ['s', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'e']
  n = 0;
  $MAP.each { |tmp_str|
   if(tmp_str.index(tmp_s))
    pathArray[i][m] = arrDouble[n][tmp_str.index(tmp_s)];
    break;
   end
   n = n + 1;
  }
  m = m + 1;
 end
  
  
 break;
end
j = j + 1;
}

i = i + 1;
puts ;
puts ;
end

#output pathArray
if(1 == 1)
x = 0;
while(x < 11)
y = 0;
while(y < 12)
 print pathArray[x][y].to_s + ' ';
 y = y + 1;
end
puts ;
x = x + 1;
end
end

pick_cost = 1+2+5+7+20+15+9+17+35+89;

min_cost = 9999999;

indexArray = [1,2,3,4,5,6,7,8,9,10];

for i1 in indexArray
indexArray.delete(i1);
tmp_cost1 = pick_cost + pathArray[0][i1];
cost1 = 1 + $COST[i1 - 1];
for i2 in indexArray
indexArray.delete(i2);
tmp_cost2 = tmp_cost1 + pathArray[i1][i2] * cost1;
cost2 = cost1 + $COST[i2 - 1];
for i3 in indexArray
 indexArray.delete(i3);
 tmp_cost3 = tmp_cost2 + pathArray[i2][i3] * cost2;
 cost3 = cost2 + $COST[i3 - 1];
 for i4 in indexArray
  indexArray.delete(i4);
  tmp_cost4 = tmp_cost3 + pathArray[i3][i4] * cost3;
  cost4 = cost3 + $COST[i4 - 1];
  for i5 in indexArray
   indexArray.delete(i5);
   tmp_cost5 = tmp_cost4 + pathArray[i4][i5] * cost4;
   cost5 = cost4 + $COST[i5 - 1];
   for i6 in indexArray
    indexArray.delete(i6);
    tmp_cost6 = tmp_cost5 + pathArray[i5][i6] * cost5;
    cost6 = cost5 + $COST[i6 - 1];
    for i7 in indexArray
     break if(min_cost <= tmp_cost6);
     indexArray.delete(i7);
     tmp_cost7 = tmp_cost6 + pathArray[i6][i7] * cost6;
     cost7 = cost6 + $COST[i7 - 1];
     for i8 in indexArray
      break if(min_cost <= tmp_cost7);
      indexArray.delete(i8);
      tmp_cost8 = tmp_cost7 + pathArray[i7][i8] * cost7;
      cost8 = cost7 + $COST[i8 - 1];
      for i9 in indexArray
       #puts 'start->'+i1.to_s+'->'+i2.to_s+'->'+i3.to_s+'->'+i4.to_s+'->'+i5.to_s+'->'+i6.to_s+'->'+i7.to_s+'->'+i8.to_s+'->'+i9.to_s+'->'+indexArray[0].to_s+'->end';
       break if(min_cost <= tmp_cost8);
       indexArray.delete(i9);
       tmp_cost9 = tmp_cost8 + pathArray[i8][i9] * cost8;
       cost9 = cost8 + $COST[i9 - 1];
       tmp_cost10 = tmp_cost9 + pathArray[i9][indexArray[0]] * cost9;
       cost10 = cost9 + $COST[indexArray[0] - 1];
       tmp_cost = tmp_cost10 + pathArray[indexArray[0]][11] * cost10;
       if(min_cost > tmp_cost)
         min_cost = tmp_cost;
         puts 'start->'+i1.to_s+'->'+i2.to_s+'->'+i3.to_s+'->'+i4.to_s+'->'+i5.to_s+'->'+i6.to_s+'->'+i7.to_s+'->'+i8.to_s+'->'+i9.to_s+'->'+indexArray[0].to_s+'->end';
         puts min_cost;
       end
       indexArray.push(i9);
       indexArray.sort!;
      end
      indexArray.push(i8);
      indexArray.sort!;
     end
     indexArray.push(i7);
     indexArray.sort!;
    end
    indexArray.push(i6);
    indexArray.sort!;
   end
   indexArray.push(i5);
   indexArray.sort!;
  end
  indexArray.push(i4);
  indexArray.sort!;
 end
 indexArray.push(i3);
 indexArray.sort!;
end
indexArray.push(i2);
indexArray.sort!;
end
indexArray.push(i1);
indexArray.sort!;
end

puts min_cost;

消息來源