題目描述：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?InputYou’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.OutputOn each line, output the minimum amount of steps starting from ‘L’, gather all the nuts, and back to ‘L’.Note: In the sample below, Larry and Ryan will go south for a nut, then south again for another nut, then south twice for another nut, and then back where they are.

題目大意：一個人位于地圖中 L 的位置，想要得到所有 # 位置的堅果再走回 L 處，所需要的最短步數？

解題思路：這是我做的第一道狀態壓縮dp，最開始遲遲找不到頭緒，不知道該如何確定狀態，看了書中的提示，才想到了辦法，獨立推出了狀態轉移方程，代碼也有很多值得思考的細節。

1、讀入數據預處理每一個堅果的位置和L的位置

2、預處理堅果和堅果（或 L ）之間的距離

3、狀態定義：dp[i][j] -> 在j這種狀態下，最后一個收集的堅果為i的情況下所走的最短步數

     狀態轉移：dp[k][j+(1<<(k-1))] = min( dp[k][j+(1<<(k-1))], dp[i][j] + a[i][k]);//a[i][k]表示第i個堅果和第k個堅果之間的距離

注意： 先循環狀態 j，在每個狀態下循環 i

這里解釋一下為什么是這樣的次序，只管來說，問題的關鍵就在于確定前往若干個#的次序，從 i 到 k 就代表著k的前一位是i的情況，因為需要用dp[i][j] 來更新別的數據，所以一定要保證dp[i][j]是已經更新完成的。所以先循環 i 無法保證 在狀態j下所有的排列次序已經走完。

AC代碼：

#include <iostream>#include <cmath>#include <cstring>#include <cstdio>#define Fori(x) for(int i=0;i<x;i++)#define Forj(x) for(int j=0;j<x;j++)#define maxn 105#define inf 0x3f3f3f3f#define ONES(x) __builtin_popcount(x)using namespace std;typedef long long ll ;const double eps =1e-8;const int mod = 1000000007;typedef pair<int, int> P;const double PI = acos(-1.0);int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int n,m;int ans;int a[20][20];char map[30][30];int dp[30][1<<20];// dp[i][j] -> 在j這種狀態下，最后一個收集的堅果為i的情況下所走的最短步數int x[30],y[30];int main(){    //freopen("test.txt","r",stdin);    while(cin>>n>>m)    {    	int num = 0;    	for(int i = 1; i<=n; i++){    		scanf("%s", map[i] + 1);    		for(int j = 1; j<=m; j++){//預處理每一個堅果的位置和L的位置    			if(map[i][j]=='#'){    				x[++num] = i;    				y[num] = j;    			}    			else if(map[i][j]=='L'){    				x[0] = i;    				y[0] = j;    			}    		}    	}    	if(num==0){    		cout << 0 << endl;    		continue;    	}    	for(int i = 0; i<=num; i++)//預處理堅果和堅果（或 L ）之間的距離    		for(int j = 0; j<=num; j++)    			a[i][j] = max(abs(x[i]-x[j]),abs(y[i]-y[j]));    	int up = (1<<num) - 1;    	memset(dp,inf,sizeof(dp));    	for(int i = 1; i<=num; i++)    		dp[i][1<<(i-1)] = a[0][i];        for(int j = 0; j<up; j++)//要注意i，j兩層循環的次序    	{    		for(int i = 1; i<=num; i++)    		{    			if( (1<<(i-1)) & j)//第i個堅果一定要包含在j這種狀態里    			for(int k = 1; k<=num; k++)    			{    				if(k!=i && !(j & (1<<(k-1))))//第k個堅果一定不在j這種狀態里    					dp[k][j+(1<<(k-1))] = min( dp[k][j+(1<<(k-1))], dp[i][j] + a[i][k]);    			}    		}    	}    	int ans = inf;    	for(int i = 1; i<=num; i++)    		ans = min(ans, dp[i][up] + a[i][0]);    	cout << ans << endl;    }    return 0;}