거미 표
거미 패 는 windows xp 운영 체제 에서 자체 적 으로 가지 고 있 는 카드 게임 이다. 게임 규칙 은 다음 과 같다. 카드 를 그녀 보다 큰 카드 위로 끌 어 올 릴 수 밖 에 없다 (A 가 가장 작고 K 가 가장 크다). 만약 에 끌 어 올 린 카드 에 순서대로 배열 한 카드 가 있 을 때 이 카드 들 도 함께 이동 하 는 것 이다. 게임 의 목적 은 모든 카드 를 같은 색깔 로 어 릴 때 부터 큰 줄 로 늘 어 놓 는 것 이다. 간단 한 견 해 를 위해 서 이다.우리 의 게임 은 같은 색깔 의 10 장의 카드 만 있 습 니 다. A 에서 10 까지 무 작위 로 한 줄 에서 펼 쳐 집 니 다. 번 호 는 1 에서 10 까지 입 니 다. i 번 의 카드 를 j 번 카드 로 옮 기 고 이동 거 리 는 abs (i - j) 입 니 다. 지금 당신 이 해 야 할 일 은 게임 을 완성 하 는 최소 이동 거 리 를 구 하 는 것 입 니 다.
입력
첫 번 째 입력 데 이 터 는 T 로 데 이 터 를 나타 내 는 그룹 수 입 니 다.
각 조 의 데 이 터 는 한 줄, 10 개의 입력 데이터 가 있 고 데이터 의 범 위 는 [1, 10] 이 며 각각 A 에서 10 을 나타 낸다. 우 리 는 각 조 의 데이터 가 모두 합 법 적 이라는 것 을 보증한다.
출력
각 그룹의 데이터 출력 최소 이동 거리 에 대응 합 니 다.
샘플 입력
1
1 2 3 4 5 6 7 8 9 10
샘플 출력
9
dfs 검색, 검색 전략 은 매번 10 장의 카드 를 매 거 하여 어느 카드 위 에 놓 을 수 있 는 지 보 는 것 입 니 다.
깊이 뒤 져 보 세 요. 먼저 매번 어떤 카드 를 움 직 이 는 지 매 거 진 다음 에 현재 의 이 카드 가 어느 카드 로 이동 해 야 하 는 지 판단 하 세 요.
주의: 예 를 들 면 2, 3, 4, 1.....................................................................................
꼭 가지치기 최적화.판단 하고 검색 해.
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int ans;//
int a[11];//
int mark[11];//
void dfs(int num,int sum) //num ,sum
{
int i,j;
if(sum>=ans)// ,ans
return;
if(num==9) // 9 , 9 , , 。
{
ans=sum;
return;
}
for(i=1;i<10;i++)
{
if(!mark[i])//
{
mark[i]=1;//
for(j=i+1;j<=10;j++) // ,j , i , 1.
{
if(!mark[j])
{
dfs(num+1,sum+abs(a[j]-a[i]));
break; // , , 。
}
}
mark[i]=0;//
}
}
}
int main()
{
int t;
cin>>t;
int x;
while(t--)
{
for(int i=1;i<=10;i++)
{
cin>>x; a[x]=i;// i ,a[i]
}
memset(mark,0,sizeof(mark));//
ans=100000;
dfs(0,0);
cout<<ans<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
물체 검출의 평가 지표 IoU의 계산 방법Yolo나 SSD 등 물체 검출에서 평가 지표로 사용되는 IoU에 대해 조사했으므로 정리했습니다. IoU (Intersection over Union)는 두 영역이 얼마나 겹치는지를 나타내는 지표입니다. 두 영역의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.