uva 1548 - The Game of Master - Mind (dfs + 가지치기)
제목: 현재 ACM 회 사 는 모 바 일 게임 을 개발 하려 고 합 니 다. 게임 은 대체적으로 숫자 를 맞 추 는 것 입 니 다. 처음에 p, c 와 m, p 는 숫자 를 맞 추 는 개수 이 고 c 는 모든 숫자의 최대 상한 선 이 며 m 는 이미 맞 춘 횟수 입 니 다. 시스템 이 맞 힐 때마다 해당 하 는 답장 힌트 를 드 리 기 때문에 다음 에 2 * m 행위 전 m 번 의 힌트 가 있 습 니 다.각 조 의 힌트 는 두 줄 로 나 뉘 는데 한 줄 은 현재 맞 힌 숫자 가 각각 어떤 것 이 있 는 지, 한 줄 은 검 은 점 개수 와 흰 점 개 수 를 대표 하 는 것 이다. 이른바 검 은 점 개수, 즉 현재 맞 힌 숫자 가 몇 개 와 답 의 위치 이 고 색깔 이 모두 같다 (문제 에서 숫자 로 색 을 대표 한다) 는 것 이다. 흰 점 은 색깔 이 같 고 위치 가 다른 점 이다.주의해 야 할 것 은 검 은 점 과 흰 점 이 일일이 대응 하 는 것 이다.지금 은 답 과 가장 가 까 운 서열 을 찾 아야 한다. 즉, 이전에 맞 힌 m 차 의 서열 을 만족 시 키 고 사전 의 순서 가 가장 작 아야 한다.
문제 풀이 방향: dfs, 하지만 dfs 만 있 으 면 복잡 도 는 100 ^ 10 입 니 다.당시 에는 제목 에 주어진 한정 조건 이 유 난 히 많 았 기 때문에 그 과정 에서 검 은 점 과 흰 점 의 상황 을 판단 하면 시간 적 으로 문제 가 없 었 다.
그러나 검 은 점 과 흰 점 을 판단 할 때 주의해 야 한다. 통 계 를 할 때 검 은 점 의 개수 와 점 수 를 합 쳐 야 한다. 검 은 점 과 흰 점 을 나 누 어 계산 하면 비교적 번 거 로 울 수 있 기 때문이다. guess 1: 21, 검 은 1, 흰 0 이 라 고 하면 ans 는 1 로 만족 하지만 dfs 0 층 에 서 는 ans 중의 첫 번 째 1 이 흰 점 이 되 기 때문이다.가 지 를 자 르 는 것 이 흰 점 이 고 개 수 는 0 으로 돌아 오 면 틀 립 니 다.제 처리 방법 은 검 은 점 에 먼저 선불 할 수 있 는 것 처럼 느껴 지지 만 선불 에 도 한도 가 있 습 니 다. 기 존 검 은 점 의 개 수 를 초과 하면 안 됩 니 다.
#include <stdio.h>
#include <string.h>
const int N = 105;
const int M = 15;
int p, c, m, b[N], w[N], ans[M];
int g[N][M], l[N][N], r[N][N];
int cnt[N], sum[N];
void init () {
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
memset(cnt, 0, sizeof(cnt));
memset(sum, 0, sizeof(sum));
scanf("%d%d%d", &p, &c, &m);
for (int i = 0; i < m; i++) {
for (int j = 0; j < p; j++) {
scanf("%d", &g[i][j]);
r[i][g[i][j]]++;
}
scanf("%d%d", &b[i], &w[i]);
}
}
inline bool judge (int x, int d) {
for (int i = 0; i < m; i++) {
if (x == g[i][d]) {
if (b[i] == cnt[i]) return false;
} else if (l[i][x] < r[i][x]) {
if (sum[i] >= w[i] + b[i]) return false;
}
}
return true;
}
inline void set (int x, int d, int flag) {
if (flag > 0) {
for (int i = 0; i < m; i++) {
if (x == g[i][d])
cnt[i]++;
if (l[i][x] < r[i][x])
sum[i]++;
l[i][x]++;
}
} else {
for (int i = 0; i < m; i++) {
if (x == g[i][d])
cnt[i]--;
l[i][x]--;
if (l[i][x] < r[i][x])
sum[i]--;
}
}
}
bool dfs (int d) {
if (d == p) {
for (int i = 0; i < m; i++)
if (cnt[i] != b[i] || sum[i] != w[i] + b[i]) return false;
return true;
}
for (int i = 1; i <= c; i++) {
if (!judge(i, d)) continue;
set(i, d, 1);
ans[d] = i;
if (dfs(d+1)) return true;
set(i, d, -1);
}
return false;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init ();
bool flag = dfs(0);
if (flag) {
printf("%d", ans[0]);
for (int i = 1; i < p; i++)
printf(" %d", ans[i]);
printf("
");
} else
printf("You are cheating!
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.