HDU 1584 蜘蛛牌

冷不防 2022-06-08 14:45 128阅读 0赞

//题意自己看，不会度娘

#include <bits/stdc++.h>
    using namespace std;
    int a[100],mark[100];
    int mmp;
    void DFS(int num,int sum)
    {	
    	if(sum>=mmp)//如果目前移动距离已经超过或等于记录的最小移动距离 
    		return ;
    	if(num==9)//10个数字需循环DFS九次 
    	{
    		if(sum<mmp) 
    		mmp=sum;//如果循环完后的移动距离小于目前的最小距离，记录 
    		return ;
    	}
    	for(int i=1;i<10;i++)//第一个循环是对所有的数字进行循环 
    	{
    		if(!mark[i])//如果没有被用过 
    		{
    			mark[i]=1;//标记 
    			for(int j=i+1;j<=10;j++)//将i这个数在所有的数里进行循环，寻找位置. 
    			{	
    				if(!mark[j])
    				{
    					DFS(num+1,sum+abs(a[j]-a[i]));
    					/*
    						举个例子。数据132654(没必要举例到10，太麻烦，这几个够了) 
    						第一次循环完后num为1,sum为1
    						第二次循环后为DFS(2,2);
    						第三次循环后为DFS(3,a[4]-a[3])   a[4]-a[3]=4,所以为DFS(3,6)
    						现在应该明白一些了吧
    						意思就是说先存下数字1到10的位置，在循环时直接找代表数字位置a[i]和b[j],例如把a[4]-a[3]相当于直接找牌三到牌四的的距离，
    						避免了移动一张牌会引起一堆牌的位置移动的问题(例如移动3就需要移动牌1和2)。
    						还是不懂的话就自己造数据放入DFS循环里想想，还是很简单的。 
    					*/ 
    					break;
    				}
    			}
    			mark[i]=0;//循环失败，重新循环	
    		}
    	}	
    }  
    int main(int argc, char *argv[])
    {
    	int n,m,t;
    	scanf("%d",&n);
    	while(n--)
    	{
    		for(int i=1;i<=10;i++)
    		{
    			scanf("%d",&t);
    			a[t]=i;
    		}
    		memset(mark,0,sizeof(mark));
    		mmp=9999;
    		DFS(0,0);
    		printf("%d\n",mmp);
    	}		
    	return 0;
    }

//Strat-ZJ-ZJ

//2017/9/28/16:07