超強瘦性!人氣內搭褲290金豪禮★拿現金最實在!法人:14檔今年本業虧定了學生退場 NHK:馬面...
2012-10-06 13:32:19 人氣(310) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][TSP] 10944 - Nuts for nuts..

0
收藏
0
推薦

Problem B: Nuts for nuts..

So as Ryan and Larry decided that they don't really taste so good, they realized that there are some nuts located in certain places of the island.. and they love them! Since they're lazy, but greedy, they want to know the shortest tour that they can use to gather every single nut!

Can you help them?

Input

You'll be given x, and y, both less than 20, followed by x lines of y characters each as a map of the area, consisting sorely of ".", "#", and "L". Larry and Ryan are currently located in "L", and the nuts are represented by "#". They can travel in all 8 adjacent direction in one step. See below for an example. There will be at most 15 places where there are nuts, and "L" will only appear once.

Output

On each line, output the minimum amount of steps starting from "L", gather all the nuts, and back to "L".

Sample Input

5 5
L....
#....
#....
.....
#....
5 5
L....
#....
#....
.....
#....

Sample Output

8
8

TSP 問題

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define oo 32767
#define min(x, y) ((x) < (y) ? (x) : (y))

int g[20][20], dp[1<<18][18], t2[1<<18];
void tsp(int state, int last) {
if(dp[state][last] != oo) return;
int i, j, tmp;
dp[state][last]--;
for(i = state; i; i -= j) {
j = i&(-i);
tsp(state-j, t2[j]);
tmp = dp[state-j][t2[j]]+g[t2[j]][last];
dp[state][last] = min(dp[state][last], tmp);
}
}
int main() {
int n, m, i, j, k, x[20], y[20];
char s[30];
for(i = 0; i < 18; i++) t2[1<<i] = i;
while(scanf("%d %d", &n, &m) == 2) {
int nut = 1;
for(i = 0; i < n; i++) {
scanf("%s", s);
for(j = 0; s[j]; j++) {
if(s[j] == '#')
x[nut] = i, y[nut++] = j;
if(s[j] == 'L')
x[0] = i, y[0] = j;
}
}
for(i = 0; i < nut; i++) {
for(j = 0; j < nut; j++) {
for(k = 0; ; k++)
if(x[i]+k >= x[j] && x[i]-k <= x[j] &&
y[i]+k >= y[j] && y[i]-k <= y[j]) {
g[i][j] = k;
break;
}
}
}
for(i = 1<<nut; i >= 0; i--)
for(j = 0; j < nut; j++)
dp[i][j] = oo;
dp[0][0] = 0;
tsp((1<<nut)-1, 0);
printf("%d\n", dp[(1<<nut)-1][0]);
}
return 0;
}
 

10944Nuts for nuts..
台長:Morris
人氣(310) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][樹走訪] 10562 - Undraw the Trees
此分類上一篇:[UVA][二分搜] 11876 - N + NOD (N)

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文