9 도 1140 - 역 추적

체스 를 할 줄 아 는 사람들 은 황 후 는 가로, 세로, 사선 에서 걸음 수 를 제한 하지 않 고 다른 바둑 알 을 먹 을 수 있다 는 것 을 잘 알 고 있다.어떻게 8 개의 황 후 를 바둑판 위 에 놓 습 니까?이것 이 바로 유명한 8 황후 문제 다.
한 황후 q (x, y) 는 다음 과 같은 조건 을 만족 시 킬 수 있 는 황후 q (row, col) 에 게 먹 힐 수 있다.
x = row (세로 로 두 황후 가 있 으 면 안 된다)
y = col (가로)
col + row = y+x;(정방 향 으로 비스듬히)
col - row = y-x;(반대 방향 으로 비스듬히)
8 황후 문 제 는 데이터 구조 서 에 설명 되 어 있 으 며 우 리 는 역 추적 사상 을 사용한다.모든 줄 에 한 명의 황후 만 놓 을 수 있 기 때문에 우 리 는 모든 줄 로 돌아 가 황후 가 모든 열 에 놓 인 상황 을 순환 합 니 다. 만약 에 위의 8 황후 의 조건 을 만족 시 키 면 이 곳 에서 황 후 를 놓 고 다음 줄 로 돌아 가 마지막 줄 에 놓 았 다 는 것 을 알 게 됩 니 다.
이 문 제 는 몇 번 째 상황 을 선택 하 라 는 것 이기 때문에 우 리 는 92 가지 상황 을 미리 기록 하면 많은 시간 을 절약 할 수 있다.

#include<stdio.h>
#include<string.h>

int data[100][8]={0};
int tmp[8]={0};
int count;
int valid(int x,int y){
	int j;
	for(int i=0;i<x;i++){
		j=tmp[i];
		if(j==y)
			return 0;
		if(i==x)
			return 0;
		if((j+i)==(x+y))
			return 0;
		if((y-x)==(j-i))
			return 0;
	}
	return 1;
}
void copy(){
	for(int i=0;i<8;i++)
		data[count][i]=tmp[i]+1;

}
void process(int ind){
	for(int i=0;i<8;i++){
		if(valid(ind,i)){
			tmp[ind]=i;
			if(ind==7){
				copy();count++;return;
			}
			process(ind+1);
			tmp[ind]=0;
		}
	}
}

int main(){
	count=0;
	process(0);
	int n,m;
	scanf("%d",&n);
	while(n--){
		scanf("%d",&m);
		for(int i=0;i<8;i++)
			printf("%d",data[m-1][i]);
		printf("
");
	}
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

제목 1069: 학생 정보 찾기

제목 설명: N 명의 학생 정 보 를 입력 하고 조회 합 니 다. 입력: 입력 한 첫 번 째 행동 N, 즉 학생 의 개수 (N < = 1000) 다음 N 줄 은 N 개 학생 의 정 보 를 포함 하고 정보 형식 은 다...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

9 도 1140 - 역 추적 - 8 황후

좋은 웹페이지 즐겨찾기