HDU 1584スパイダーソリティア（DFS）

Hdu 1584 Spider Solitaire

制限時間：10000/5000 MS（Java /その他）メモリ制限：32768/32768 K（Java /その他）
提出総数：4818承認された提出：2052


問題の説明スパイダーカードは、WindowsXPオペレーティングシステムに付属しているカードゲームです。ゲームのルールは次のとおりです。ドラッグしたカードにボタンがある場合、カードを順番に並べると、カードを自分より1つ高いカード（最小のA、最大のK）にのみドラッグできます。 、その後、これらのカードは一緒に移動します。ゲームの目的は、小さいものから大きいものまで、すべてのカードを同じスーツに配置することです。簡単にするために、私たちのゲームにはAから10までの同じスーツのカードが10枚しかなく、1から10までの番号が1行にランダムに展開されます。i番目のカードのカードをj番目のカードに移動します。 、移動距離はabs（ij）です。次に、ゲームの完了を見つける必要があります。最小移動距離。

入力最初の入力データはTで、データのグループの数を表します。
データの各グループには1つの行、10の入力データがあり、データの範囲は[1,10]で、それぞれAから10を表します。データの各グループが合法であることを保証します。
出力データ出力の最小移動距離の各グループに対応します。
サンプル入力#include #include #include #define Max 999999 #include using namespace std int visit[20] int map[20] int ans void dfs(int cnt,int sum) { if(sum>ans) { return } if(cnt==9) { ans=sum } int i,j for(i=1i<10i++) { if(visit[i]==0) { visit[i]=1 for(j=i+1j<=10j++) { if(visit[j]==0) { dfs(cnt+1,sum+abs(map[i]-map[j])) break } } visit[i]=0 } } } int main(int argc, char *argv[]) { int t scanf('%d',&t) while(t--) { int a,i for(i=1i<=10i++) { scanf('%d',&a) map[a]=i } ans=999999 memset(visit,0,sizeof(visit)) dfs(0,0) printf('%d ',ans) } return 0 } 1 1 2 3 4 5 6 7 8 9 10
サンプル出力

9
すべての状況をトラバースするだけで十分であり、減らす必要があります。つまり、現在の状況のステップ数が以前に完了した最小ステップ数よりも多い場合、現在のトラバースは無意味であり、スキップできます。 彼の位置を保存して値を記録する必要があるため、この質問の保存にも注意が必要です。そのため、配列の添え字が値として使用され、配列の値を位置として使用できます。