首页 > 代码库 > hdu1584 深搜水题
hdu1584 深搜水题
牌移动的步数为牌所在位置差的绝对值
这道题用到深搜 每次出差跑牌面为1-9的牌 如果没移动过则尝试移动 如果能移动 就深搜下去 注意回溯
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int mark[15],num[15],Min; int abs(int a) { return a>0?a:-a; } int dfs(int sum,int coun) { int i,j; if(sum>Min) return 0;//这里是一个优化 好像没有就会超时吧 if(coun==9) { Min=sum; return 0; } for(i=1;i<10;i++)//列举1-9张牌 应为第10 号牌一定不用移动 { if(!mark[i]) { for(j=i+1;j<=10;j++)//找到牌i能移到的牌 { if(!mark[j]) { mark[i]=1; dfs(sum+abs(num[j]-num[i]),coun+1); break; } } mark[i]=0;//回溯 } } return 0; } int main() { int i,T,a; scanf("%d",&T); while(T--) { for(i=1;i<=10;i++) { scanf("%d",&a); num[a]=i;//记录每张牌所在位置 } memset(mark,0,sizeof(mark)); Min=9999999; dfs(0,0); printf("%d\n",Min); } return 0; }} return 0;}
hdu1584 深搜水题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。