/*******************************************************************************
ブロック・バイ・ブロックス
２００１．９出題
******************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define NON -1 /* 直方体のその場所にブロックは置かれてない /*
#define CB(X , Y , Z) (Z) * xy1 + (Y) * (size.x) + (X) /* ブロック座標変換 /*
typedef struct {
int x; /* Ｘ /*
int y; /* Ｙ /*
int z; /* Ｚ /*
} XYZ; /* 座標定義構造体 /*
typedef struct {
int x; /* Ｘ /*
int y; /* Ｙ /*
int z; /* Ｚ /*
int b; /* 置いたブロックの種類(0-5) /*
} XYZB; /* ブロック構造体 /*
int *cube = NULL; /* 直方体の各座標のブロック番号を格納する /*
XYZ size; /* 直方体のサイズ /*
int xy1; /* 直方体のＸ方向、Ｙ方向のサイズの積 /*
int *rx1 = NULL , *ry1 = NULL , *rz1 = NULL;
/* その座標をまたぐブロックの数。１以上ならそこでスパッとは切れない /*
int count = 0; /* パターンの数 /*
XYZB *pat1 = NULL; /* 置いた全ブロックの情報 /*
XYZB *pat2 = NULL; /* 題意を満たすブロックパターンを全て格納する /*
static XYZ blk1[] = {3,2,1 , 2,3,1 , 3,1,2 , 2,1,3 , 1,3,2 , 1,2,3};
/* ブロック(６個)の定義 /*
XYZ blk2[6][5]; /* ブロックの座標定義 /*
/*******************************************************************************
機能：一処理、または全処理後のメモリ開放
引数：なし
戻り値：なし
******************************************************************************/*
void memFree(void)
{
free(cube);
free(rx1);
free(ry1);
free(rz1);
free(pat1);
free(pat2);
cube = rx1 = ry1 = rz1 = NULL;
pat1 = NULL;
}
/*******************************************************************************
機能：初期化処理（blk2に値を設定）
引数：なし
戻り値：なし
******************************************************************************/*
void init(void)
{
int i , j , x , y , z;
for(i = 0 ; i < 6 ; i++) {
j = 0;
for(z = 0 ; z < blk1[i].z ; z++) {
for(y = 0 ; y < blk1[i].y ; y++) {
for(x = 0 ; x < blk1[i].x ; x++) {
if(x == 0 && y == 0 && z == 0) continue;
blk2[i][j].x = x;
blk2[i][j].y = y;
blk2[i][j].z = z;
j++;
}
}
}
}
}
/*******************************************************************************
機能：切れるかどうかチェックする。
引数：なし
戻り値：OFF:切れる ON:切れない
******************************************************************************/*
int check(void)
{
int x , y , z;
for(x = 0 ; x < size.x - 1 ; x++) {
if(rx1[x] == 0) return(OFF);
}
for(y = 0 ; y < size.y - 1 ; y++) {
if(ry1[y] == 0) return(OFF);
}
for(z = 0 ; z < size.z - 1 ; z++) {
if(rz1[z] == 0) return(OFF);
}
return(ON);
}
/*******************************************************************************
機能：置いた（取り去る）ブロックがまたぐ座標をカウントアップ（ダウン)
引数：
x (I) : ブロックの基準Ｘ座標
y (I) : ブロックの基準Ｙ座標
z (I) : ブロックの基準Ｚ座標
i (I) : ブロックの種類
f1 (I) : OFF:取り去る、ON:置く
戻り値：なし
******************************************************************************/*
void funcz(int x , int y , int z , int i , int f1)
{
int d1 = 1;
if(f1 == OFF) d1 = -d1;
if(blk1[i].x > 1) rx1[x] += d1;
if(blk1[i].x == 3) rx1[x + 1] += d1;
if(blk1[i].y > 1) ry1[y] += d1;
if(blk1[i].y == 3) ry1[y + 1] += d1;
if(blk1[i].z > 1) rz1[z] += d1;
if(blk1[i].z == 3) rz1[z + 1] += d1;
}
/*******************************************************************************
機能：qsortの比較関数。座標(z,y,x)で昇順にソートする。
引数：
*a (I) : 比較元左
*b (I) : 比較元右
戻り値：-1:左大、0:等、1:右大
******************************************************************************/*
int cmp(const void *a , const void *b)
{
if(((XYZB *)a)->z < ((XYZB *)b)->z) return(-1);
else if(((XYZB *)a)->z == ((XYZB *)b)->z) {
if(((XYZ *)a)->y < ((XYZB *)b)->y) return(-1);
else if(((XYZB *)a)->y == ((XYZB *)b)->y) {
if(((XYZB *)a)->x < ((XYZB *)b)->x) return(-1);
else if(((XYZB *)a)->x == ((XYZB *)b)->x) return(0);
else return(1);
}
else return(1);
}
else return(1);
}
/*******************************************************************************
機能：鏡像などのチェック。既出鏡像でなければcountをアップする。
引数：
n (i) : ブロックの数
戻り値：なし
******************************************************************************/*
void mirror(int n)
{
int x1 , y1 , z1;
int i , j;
XYZB *t1; /* 鏡像判定用一次領域 /*
t1 = (XYZB *)malloc(sizeof(XYZB) * n);
if(t1 == NULL) {
fprintf(stderr , "t1 malloc error %s %d\n" , __FILE__ , __LINE__);
memFree();
exit(0);
}
for(i = 0 ; i < count ; i++) {
for(z1 = OFF ; z1 <= ON ; z1++) { /* Ｚ＝正or負 /*
for(y1 = OFF ; y1 <= ON ; y1++) { /* Ｙ＝正or負 /*
for(x1 = OFF ; x1 <= ON ; x1++) { /* Ｘ＝正or負 /*
for(j = 0 ; j < n ; j++) {
t1[j].x = pat2[i * n + j].x;
t1[j].y = pat2[i * n + j].y;
t1[j].z = pat2[i * n + j].z;
t1[j].b = pat2[i * n + j].b;
if(x1 == ON) t1[j].x = size.x - t1[j].x - blk1[t1[j].b].x;
if(y1 == ON) t1[j].y = size.y - t1[j].y - blk1[t1[j].b].y;
if(z1 == ON) t1[j].z = size.z - t1[j].z - blk1[t1[j].b].z;
}
qsort(t1 , n , sizeof(t1[0]) , cmp);
for(j = 0 ; j < n ; j++) {
if(t1[j].x != pat1[j].x) break;
if(t1[j].y != pat1[j].y) break;
if(t1[j].z != pat1[j].z) break;
if(t1[j].b != pat1[j].b) break;
}
if(j == n) { /* 全て一致したら既出パターン /*
free(t1);
return;
}
}
}
}
}
free(t1);
if(pat2 == 0) {
pat2 = (XYZB *)malloc(sizeof(XYZB) * n);
if(pat2 == NULL) {
fprintf(stderr , "pat2 malloc error %s %d\n" , __FILE__ , __LINE__);
memFree();
exit(0);
}
}
else {
pat2 = (XYZB *)realloc(pat2 , sizeof(XYZB) * n * (count + 1));
if(pat2 == NULL) {
fprintf(stderr , "pat2 realloc error %s %d\n" , __FILE__ , __LINE__);
memFree();
exit(0);
}
}
for(i = 0 ; i < n ; i++) { /* 新しいパターンならpat2に格納する /*
pat2[count * n + i].x = pat1[i].x;
pat2[count * n + i].y = pat1[i].y;
pat2[count * n + i].z = pat1[i].z;
pat2[count * n + i].b = pat1[i].b;
}
count++;
return;
}
/*******************************************************************************
機能：ブロックを１つ置く
引数：
x (I) : Ｘ座標
y (I) : Ｙ座標
z (I) : Ｚ座標
n (I) : これまでに置いたブロックの数−１
戻り値：なし
******************************************************************************/*
void sub2(int x , int y , int z , int n)
{
int i , j;
if(x == size.x) {
x = 0;
y++;
if(y == size.y) {
y = 0;
z++;
if(z == size.z) {
if(check() == ON) mirror(n);
return;
}
}
}
if(cube[CB(x , y , z)] != NON) { /* 既にブロックが置かれてたら次の座標へ /*
sub2(x + 1 , y , z , n);
return;
}
for(i = 0 ; i < 6 ; i++) { /* ブロック６種類について /*
for(j = 0 ; j < 5 ; j++) {
if(x + blk2[i][j].x >= size.x) break; /* 直方体Ｘ方向範囲外 /*
if(y + blk2[i][j].y >= size.y) break; /* 直方体Ｙ方向範囲外 /*
if(z + blk2[i][j].z >= size.z) break; /* 直方体Ｚ方向範囲外 /*
if(cube[CB(x + blk2[i][j].x , y + blk2[i][j].y , z + blk2[i][j].z)] != NON) break;
}
if(j < 5) continue; /* 置けないならスキップ /*
cube[CB(x , y , z)] = n; /* ブロック原点に置く /*
for(j = 0 ; j < 5 ; j++) { /* 原点以外５箇所に置く /*
cube[CB(x + blk2[i][j].x , y + blk2[i][j].y , z + blk2[i][j].z)] = n;
}
funcz(x , y , z , i , ON);
pat1[n].x = x;
pat1[n].y = y;
pat1[n].z = z;
pat1[n].b = i;
sub2(x + 1 , y , z , n + 1);
funcz(x , y , z , i , OFF);
cube[CB(x , y , z)] = NON; /* ブロック原点から取る /*
for(j = 0 ; j < 5 ; j++) { /* 原点以外５箇所から取る /*
cube[CB(x + blk2[i][j].x , y + blk2[i][j].y , z + blk2[i][j].z)] = - 1;
}
}
}
/*******************************************************************************
機能：直方体のサイズが確定した時点の初期化処理
引数：
n (I) :置くブロックの総数
戻り値：なし
******************************************************************************/*
void sub(int n)
{
int x , y , z;
xy1 = size.x * size.y;
cube = (int *)malloc(sizeof(int) * xy1 * size.z); /* 直方体作成 /*
if(cube == NULL) {
fprintf(stderr , "cube malloc error %s %d\n" , __FILE__ , __LINE__);
exit(0);
}
for(x = 0 ; x < size.x ; x++) {
for(y = 0 ; y < size.y ; y++) {
for(z = 0 ; z < size.z ; z++) cube[CB(x , y , z)] = NON;
}
}
rx1 = (int *)malloc(sizeof(int) * size.x);
if(rx1 == NULL) {
fprintf(stderr , "rx1 malloc error %s %d\n" , __FILE__ , __LINE__);
memFree();
exit(0);
}
for(x = 0 ; x < size.x ; x++) rx1[x] = 0;
ry1 = (int *)malloc(sizeof(int) * size.y);
if(ry1 == NULL) {
fprintf(stderr , "ry1 malloc error %s %d\n" , __FILE__ , __LINE__);
memFree();
exit(0);
}
for(y = 0 ; y < size.y ; y++) ry1[y] = 0;
rz1 = (int *)malloc(sizeof(int) * size.z);
if(rz1 == NULL) {
fprintf(stderr , "rz1 malloc error %s %d\n" , __FILE__ , __LINE__);
memFree();
exit(0);
}
for(z = 0 ; z < size.z ; z++) rz1[z] = 0;
pat1 = (XYZB *)malloc(sizeof(XYZB) * n);
if(pat1 == NULL) {
fprintf(stderr , "pat1 malloc error %s %d\n" , __FILE__ , __LINE__);
memFree();
exit(0);
}
sub2(0 , 0 , 0 , 0);
memFree();
}
/*******************************************************************************
機能：メイン
引数：なし
戻り値：０
******************************************************************************/*
int main(void)
{
int i = 2; /* ブロックの数。初期値は２個 /*
int s; /* 直方体の体積 /*
int t2;
init();
while(1) {
s = i * 6;
for(size.x = 2 ; size.x <= s ; size.x++) {
for(size.y = size.x ; size.y <= s ; size.y++) {
xy1 = size.x * size.y;
if(xy1 > s) break;
for(size.z = size.y ; size.z <= s ; size.z++) {
t2 = xy1 * size.z;
if(t2 < s) continue;
else if(t2 == s) sub(i);
break;
}
}
}
if(count > 0) break;
i++;
}
printf("%d個 %d通り\n" , i , count);
return(0);
}
|
第128回（11月）リング平方数
|
|
/******************************************************************************
平方数リング（Ｃマガジン２００１年８月電脳クラブ出題）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define N1 1 /* リングに配置する数の最小値（２個目固定） /*
#define N2 2 /* 平方数の元の数の最小値 /*
#define N3 3 /* リングに配置する個数の最小値 /*
int count = 0; /* 通りの数 /*
int *fUsed; /* リングで使用済みかどうかのフラグ /*
int t0; /* １個目の値 /*
/******************************************************************************
機能：再帰関数
引数：
(1) k1 (I) 設定済みの平方数の個数
(2) n (I) 調査中のリング上の平方数の個数
(3) t1 (I) １つ前に設定した値
戻り値：なし
*****************************************************************************/*
void sub(int k1 , int n , int t1)
{
int i2 = N2;
int t2;
if(k1 == n) { /* リング上全てに数を置いたら /*
while(1) {
if(t1 + t0 > i2 * i2) i2++;
else {
if(t1 + t0 == i2 * i2) count++; /* 最初と最後のチェック /*
return;
}
}
}
t2 = i2 * i2 - t1;
while(t2 <= n) {
if(t2 > 0 && fUsed[t2] == OFF) { /* 未使用なら /*
fUsed[t2] = ON; /* 使用済みにする /*
sub(k1 + 1 , n , t2); /* 次に進む /*
fUsed[t2] = OFF; /* 未使用にする /*
}
i2++;
t2 = i2 * i2 - t1;
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：０
*****************************************************************************/*
int main(void)
{
int n = N3;
int i;
int i0 , i1;
int t1; /* ３個目の値 /*
fUsed = (int *)malloc(sizeof(int) * (n));
if(fUsed == NULL) {
fprintf(stderr , "Can't malloc at %s %d\n" , __FILE__ , __LINE__);
exit(0);
}
fUsed[N1] = ON; /* １を使用済みにする /*
for(i = 2 ; i < n ; i++) fUsed[i] = OFF; /* １以外を未使用にする /*
while(1) {
fUsed = (int *)realloc(fUsed , sizeof(int) * (n + 1));
if(fUsed == NULL) {
fprintf(stderr , "Can't realloc at %s %d\n" , __FILE__ , __LINE__);
exit(0);
}
fUsed[n] = OFF;
i0 = N2;
t0 = i0 * i0 - N1; /* リング１個目 /*
while(t0 <= n) {
fUsed[t0] = ON;
i1 = i0 + 1;
t1 = i1 * i1 - N1; /* リング２個目 /*
while(t1 <= n) {
fUsed[t1] = ON;
sub(N3 , n , t1);
fUsed[t1] = OFF;
i1++;
t1 = i1 * i1 - N1; /* リング２個目 /*
}
fUsed[t0] = OFF;
i0++;
t0 = i0 * i0 - N1; /* リング１個目 /*
}
if(count > 0) break;
n++;
}
free(fUsed);
printf("%d個 %d通り\n" , n , count);
return(0);
}
|
第126回（9月）開き直り数
|
|
/******************************************************************************
Ｃマガジン２００１年６月 電脳クラブ 開き直り数
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
int r1[10]; /* それぞれの数のべき乗の値 1.1 2.4 3.27 ... /*
/******************************************************************************
機能：再帰ルーチン
引数：
(1) a1 (I) 各数字の使用する個数
(2) b1 (I) 使える最大値
(3) s1 (I) ここまでのべき乗和
(4) k (I) べき乗する数
戻り値：なし
*****************************************************************************/*
void sub1(int a1[] , int n1 , unsigned int s1 , int k)
{
unsigned int s2;
int n2;
int i , t2 , t3;
int t1[10];
for(a1[k] = 0 ; a1[k] <= n1 ; a1[k]++) {
s2 = s1 + r1[k] * a1[k];
n2 = n1 - a1[k];
if(k < 8) sub1(a1 , n2 , s2 , k + 1);
else {
a1[9] = n2;
s2 += (r1[9] * a1[9]);
t3 = 1000000000;
for(i = 0 ; i < 10 ; i++) t1[i] = 0;
for(i = 0 ; i < 10 ; i++) {
t1[(t2 = (s2 / t3) % 10)]++;
if(t1[t2] > a1[t2]) break;
t3 /= 10;
}
if(i == 10) printf("%d\n" , s2);
}
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：０
*****************************************************************************/*
int main(void)
{
int a1[10];
int i , j;
r1[0] = 0; /* r1を初期化する /*
for(i = 1 ; i < 10 ; i++) {
r1[i] = 1;
for(j = 0 ; j < i ; j++) {
r1[i] *= i;
}
}
sub1(a1 , 10 , (unsigned int)0 , 0);
return(0);
}
|
第125回（8月）REV STAR
|
|
/******************************************************************************
Ｃマガジン２００１年５月出題 REV STAR
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OMOTE 0 /* 表 /*
#define URA 1 /* 裏 /*
#define AKI 2 /* 空き /*
#define HANTEN(x) (URA - x) /* コインを反転するマクロ /*
#define N1 2304 /* パターンの数 = 3^2 * 2^8 /*
#define HIGHVALUE 1000000 /* ハイバリュー /*
#define N10 10 /* コインの個所数 /*
#define N5 5 /* 10 / 2 /*
#define NON 0 /* 次のパターン番号なし /*
int nxtPat[N1][4]; /* 次のパターン番号 /*
int b4[N1]; /* そのパターンにいたる最小手 /*
int p1[3]; /* 初期パターン、終了パターン×２種類 /*
int min = HIGHVALUE; /* 最小手数 /*
/******************************************************************************
機能：再帰ルーチン
引数：
(1) n1 (I) 現在のパターン番号
(2) n2 (I) ここまでの手数
戻り値：なし
*****************************************************************************/*
void sub(int n1 , int n2)
{
int i;
if(n1 == p1[1] || n1 == p1[2]) { /* 終了パターンか？ /*
if(n2 < min) min = n2; /* 最小手更新 /*
return;
}
if(min < n2) return; /* 最小手を越えたら探査打ち切り /*
for(i = 0 ; i < 4 ; i++) {
if(nxtPat[n1][i] == NON) break; /* 次のパターンがなければブレイク /*
if(b4[nxtPat[n1][i]] < n2) continue; /* 最小手数でなければスキップ /*
b4[nxtPat[n1][i]] = n2 + 1; /* そのパターンに至った最小手数を記録 /*
sub(nxtPat[n1][i] , n2 + 1); /* 次の手へ /*
}
}
/******************************************************************************
機能：パターン番号を求める
引数：
(1) w (I) パターン
(2) p (I) 空きの場所
戻り値：パターン番号
*****************************************************************************/*
int GetVal(int w[] , int p)
{
int i;
int s = 0;
static int r1[] = {1 , 3 , 6 , 12 , 24 , 48 , 144 , 288 , 576 , 1152};
/* パターン番号をユニークにするための箇所ごとの係数 /*
for(i = 0 ; i < N5 ; i++) { /* 空きの場所を一定にする。 /*
s += (w[(p + i) % N5] * r1[i]); /* 星の外側５個 /*
s += (w[((p + i) % N5) + N5] * r1[i + N5]); /* 星の内側５個 /*
}
return(s);
}
/******************************************************************************
機能：初期化サブ
引数：
(1) w1 (I) パターン
戻り値：なし
*****************************************************************************/*
void init2(int w1[])
{
int n = 0;
static int linPat[][4] = { /* コイン飛び越し定義 /*
0 , 9 , 8 , 3 ,
0 , 5 , 6 , 2 ,
1 , 5 , 9 , 4};
int w2 , w3[N10]; /* ワーク /*
int j , k; /* ループのインデックス /*
w2 = GetVal(w1 , 0);
b4[w2] = HIGHVALUE; /* そのパターンに至った最小手数の初期化 /*
n = 0;
if(w1[0] == AKI) { /* 外側に空がある場合 /*
for(j = 0 ; j < 2 ; j++) {
for(k = 0 ; k < N10 ; k++) w3[k] = w1[k];
w3[linPat[j][0]] = w3[linPat[j][3]]; /* 飛び先 /*
w3[linPat[j][1]] = HANTEN(w3[linPat[j][1]]); /* 通過反転 /*
w3[linPat[j][2]] = HANTEN(w3[linPat[j][2]]); /* 通過反転 /*
w3[linPat[j][3]] = AKI; /* 飛び元 /*
nxtPat[w2][n++] = GetVal(w3 , linPat[j][3]);
for(k = 0 ; k < N10 ; k++) w3[k] = w1[k];
w3[linPat[j][0]] = w3[linPat[j][2]]; /* 飛び先 /*
w3[linPat[j][1]] = HANTEN(w3[linPat[j][1]]); /* 通過反転 /*
w3[linPat[j][2]] = AKI; /* 飛び元 /*
nxtPat[w2][n++] = GetVal(w3 , linPat[j][2]);
}
}
else if(w1[5] == AKI) { /* 内側に空がある場合 /*
for(j = 1 ; j < 3 ; j++) {
for(k = 0 ; k < N10 ; k++) w3[k] = w1[k];
w3[linPat[j][1]] = w3[linPat[j][3]]; /* 飛び先 /*
w3[linPat[j][2]] = HANTEN(w3[linPat[j][2]]); /* 通過反転 /*
w3[linPat[j][3]] = AKI; /* 飛び元 /*
nxtPat[w2][n++] = GetVal(w3 , linPat[j][3]);
}
nxtPat[w2][2] = nxtPat[w2][3] = NON; /* 未使用 /*
}
}
/******************************************************************************
機能：初期化ルーチン
あるパターンから次のパターンへの遷移を全て求める。
引数：なし
戻り値：なし
*****************************************************************************/*
void init(void)
{
int w1[N10];
int i;
for(w1[0] = OMOTE ; w1[0] <= AKI ; w1[0]++) {
for(w1[1] = OMOTE ; w1[1] <= URA ; w1[1]++) {
for(w1[2] = OMOTE ; w1[2] <= URA ; w1[2]++) {
for(w1[3] = OMOTE ; w1[3] <= URA ; w1[3]++) {
for(w1[4] = OMOTE ; w1[4] <= URA ; w1[4]++) {
for(w1[5] = OMOTE ; w1[5] <= AKI ; w1[5]++) {
if(w1[0] == AKI && w1[5] == AKI) continue;
if(w1[0] != AKI && w1[5] != AKI) continue;
for(w1[6] = OMOTE ; w1[6] <= URA ; w1[6]++) {
for(w1[7] = OMOTE ; w1[7] <= URA ; w1[7]++) {
for(w1[8] = OMOTE ; w1[8] <= URA ; w1[8]++) {
for(w1[9] = OMOTE ; w1[9] <= URA ; w1[9]++) {
init2(w1);
}
}
}
}
}
}
}
}
}
}
w1[0] = AKI;
for(i = 1 ; i < N10 ; i++) w1[i] = OMOTE;
p1[0] = GetVal(w1 , 0); /* 初期パターン番号 /*
for(i = 1 ; i < N10 ; i++) w1[i] = URA;
p1[1] = GetVal(w1 , 0); /* 終了パターン番号その１ /*
w1[0] = URA;
w1[5] = AKI;
p1[2] = GetVal(w1 , 0); /* 終了パターン番号その２ /*
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：常に1
*****************************************************************************/*
int main(void)
{
init();
b4[p1[0]] = 0;
sub(p1[0] , 0);
printf("%d\n" , min);
return(0);
}
|
第124回（7月）隣差方陣
|
|
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define N2 2 /* 隣差＝±２のインデックス値 /*
#define N24 24 /* 隣差が取りうる数の種類 /*
#define RMIN 1 /* 隣差の絶対値の最小値 /*
#define RMAX 12 /* 隣差の絶対値の最大値 /*
int d1[N24]; /* 隣差がとりうる値の配列 /*
int d2[N24]; /* 隣差がとりうる値の絶対値の配列 /*
int fUsed[13]; /* 使用済みフラグ OFF=未使用、ON=使用済み /*
/******************************************************************************
機 能：隣差６個を決定して、解を求める。
引 数：
i01 INT (I) マス０−マス１の隣差のインデックス
i14 INT (I) マス１−マス４の隣差のインデックス
戻り値：パターンの数
*****************************************************************************/*
int sub(int i01 , int i14)
{
int ma0 = 0 , ma1 , ma2 , ma3 , ma4 , ma5 , ma6 , ma7 , ma8; /* マスの値 /*
int sa34 , sa45 , sa67 , sa78; /* 隣差の絶対値 /*
int i12 , i03 , i25 , i36 , i47 , i58; /* ループの制御変数 /*
int count = 0; /* パターンの数 /*
ma1 = ma0 + d1[i01];
ma4 = ma1 + d1[i14];
for(i03 = N2 ; i03 < N24 ; i03++) {
if(fUsed[d2[i03]] == ON) continue;
ma3 = ma0 + d1[i03];
sa34 = abs(ma4 - ma3);
if(sa34 < RMIN || sa34 > RMAX) continue;
if(fUsed[sa34] == ON) continue;
if(d2[i03] == sa34) continue;
fUsed[d2[i03]] = ON;
fUsed[sa34] = ON;
for(i12 = i01 + 1 ; i12 < N24 ; i12++) {
if(fUsed[d2[i12]] == ON) continue;
ma2 = ma1 + d1[i12];
if(ma2 == ma3) continue;
if(ma2 == ma4) continue;
fUsed[d2[i12]] = ON;
for(i25 = N2 ; i25 < N24 ; i25++) {
if(fUsed[d2[i25]] == ON) continue;
ma5 = ma2 + d1[i25];
if(ma0 == ma5) continue;
if(ma1 == ma5) continue;
if(ma3 == ma5) continue;
sa45 = abs(ma5 - ma4);
if(sa45 < RMIN || sa45 > RMAX) continue;
if(d2[i25] == sa45) continue;
if(fUsed[sa45] == ON) continue;
fUsed[d2[i25]] = ON;
fUsed[sa45] = ON;
for(i36 = N2 ; i36 < N24 ; i36++) {
if(fUsed[d2[i36]] == ON) continue;
ma6 = ma3 + d1[i36];
if(ma0 == ma6) continue;
if(ma1 == ma6) continue;
if(ma2 == ma6) continue;
if(ma4 == ma6) continue;
if(ma5 == ma6) continue;
fUsed[d2[i36]] = ON;
for(i47 = N2 ; i47 < N24 ; i47++) {
if(fUsed[d2[i47]] == ON) continue;
ma7 = ma4 + d1[i47];
if(ma0 == ma7) continue;
if(ma1 == ma7) continue;
if(ma2 == ma7) continue;
if(ma3 == ma7) continue;
if(ma5 == ma7) continue;
sa67 = abs(ma7 - ma6);
if(sa67 < RMIN || sa67 > RMAX) continue;
if(d2[i47] == sa67) continue;
if(fUsed[sa67] == ON) continue;
fUsed[d2[i47]] = ON;
fUsed[sa67] = ON;
for(i58 = N2 ; i58 < N24 ; i58++) {
if(fUsed[d2[i58]] == ON) continue;
ma8 = ma5 + d1[i58];
if(ma0 == ma8) continue;
if(ma1 == ma8) continue;
if(ma2 == ma8) continue;
if(ma3 == ma8) continue;
if(ma4 == ma8) continue;
if(ma6 == ma8) continue;
sa78 = abs(ma8 - ma7);
if(sa78 < RMIN || sa78 > RMAX) continue;
if(fUsed[sa78] == ON) continue;
if(d2[i58] == sa78) continue;
count++;
}
fUsed[d2[i47]] = OFF;
fUsed[sa67] = OFF;
}
fUsed[d2[i36]] = OFF;
}
fUsed[d2[i25]] = OFF;
fUsed[sa45] = OFF;
}
fUsed[d2[i12]] = OFF;
}
fUsed[sa34] = OFF;
fUsed[d2[i03]] = OFF;
}
return(count);
}
/******************************************************************************
機 能：メイン（隣差２個を決定する）
引 数：なし
戻り値：1
*****************************************************************************/*
int main(void)
{
int i0 , i1 = 0;
int count = 0; /* パターンの数 /*
for(i0 = RMIN ; i0 <= RMAX ; i0++) {
fUsed[i0] = OFF; /* 使用済みフラグをOFFにする /*
d2[i1] = d2[i1 + 1] = i0; /* 絶対値 /*
d1[i1++] = i0; /* 正 /*
d1[i1++] = - i0; /* 負 /*
}
for(i0 = 0 ; i0 < N2 ; i0++) {
fUsed[d2[i0]] = ON;
for(i1 = N2 ; i1 < N24 ; i1++) {
fUsed[d2[i1]] = ON;
count += sub(i0 , i1);
count += sub(i1 , i0);
fUsed[d2[i1]] = OFF;
}
fUsed[d2[i0]] = OFF;
}
printf("%d\n" , count);
return(0);
}
|
第123回（6月）六角形の超線上
|
|
/******************************************************************************
C MAGAZINE 2001.03
六角形の超線上
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define N2 2 /* 線上に置けるコインの最大値 /*
#define N11 11 /* 鏡像などのパターンの数 /*
#define N12 12 /* 線分の傾きの数 /*
#define N36 36 /* N37 - 1 /*
#define N37 37 /* マスの数 /*
#define NF -1 /* マス番号がない場合 /*
typedef struct {
int org[N12]; /* 通過する座標の基準座標番号 /*
int count[N12]; /* 線分上の個数 /*
} C1;
typedef struct {
int x;
int y;
} XY;
C1 c1[N37];
XY d1[N37] = {
3,0, 5,0 , 7,0 , 9,0 ,
2,1 , 4,1 , 6,1 , 8,1 , 10,1 ,
1,2 , 3,2 , 5,2 , 7,2 , 9,2 , 11,2 ,
0,3 , 2,3 , 4,3 , 6,3 , 8,3 , 10,3 , 12,3 ,
1,4 , 3,4 , 5,4 , 7,4 , 9,4 , 11,4 ,
2,5 , 4,5 , 6,5 , 8,5 , 10,5 ,
3,6, 5,6 , 7,6 , 9,6};
XY e1[N12] = { /* 線の傾き定義 /*
0 , 2 ,
1 , 1 , -1 , 1 ,
2 , 0 ,
1 , 3 , -1 , 3 ,
3 , 1 , -3 , 1 ,
4 , 2 , -4 , 2 ,
5 , 1 , -5 , 1};
int max = 6; /* 置いたコインの最大値（最低６個（頂点の数）は置ける） /*
int count = 0; /* maxのパターン数 /*
int f1[N37]; /* 座標毎のコインを置いたかどうかのフラグ /*
int *r1 = NULL; /* パターンの保存 /*
int MrPt2[N11][N37]; /* 鏡像などのチェックパターン /*
/******************************************************************************
機 能：鏡像などの重複パターンをチェックする。
引 数：なし
戻り値：なし
*****************************************************************************/*
void check(void)
{
int i , j , k;
int p1;
/* 既出パターンにあるかどうか調べる /*
for(i = 0 ; i < count ; i++) {
p1 = i * N37;
for(j = 0 ; j < N11 ; j++) {
for(k = 0 ; k < N37 ; k++) {
if(f1[k] != r1[p1 + MrPt2[j][k]]) break;
}
if(k == N37) return;
}
}
/* もしなければ登録する /*
r1 = (int *)realloc(r1 , sizeof(int) * (count + 1) * N37);
if(r1 == NULL) {
fprintf(stderr , "メモリ確保エラー\n");
exit(0);
}
for(k = 0 ; k < N37 ; k++) r1[count * N37 + k] = f1[k];
count++;
}
/******************************************************************************
機 能：その座標の番号を求める。
引 数：
x INT (I) Ｘ座標
y INT (I) Ｙ座標
戻り値：見つかった場合はその座標の番号。
見つからなかった場合はNF。
*****************************************************************************/*
int umu(int x , int y)
{
int i;
for(i = 0 ; i < N37 ; i++) {
if(x == d1[i].x && y == d1[i].y) return(i);
}
return(NF);
}
/******************************************************************************
機 能：初期化処理
引 数：なし
戻り値：なし
*****************************************************************************/*
void init()
{
int i , j , k;
int t0 , t1;
static int MrPt1[][N37] = {
15, 9, 4, 0, /* 回転パターン /*
22, 16, 10, 5, 1,
28, 23, 17, 11, 6, 2,
33, 29, 24, 18, 12, 7, 3,
34, 30, 25, 19, 13, 8,
35, 31, 26, 20, 14,
36, 32, 27, 21,
3, 2, 1, 0, /* 左右反転パターン /*
8, 7, 6, 5, 4,
14, 13, 12, 11, 10, 9,
21, 20, 19, 18, 17, 16, 15,
27, 26, 25, 24, 23, 22,
32, 31, 30, 29, 28,
36, 35, 34, 33
};
for(i = 0 ; i < N37 ; i++) {
f1[i] = OFF;
for(j = 0 ; j < N12 ; j++) {
c1[i].org[j] = NF;
c1[i].count[j] = 0;
}
}
for(i = 0 ; i < N37 ; i++) {
for(j = 0 ; j < N12 ; j++) {
if(c1[i].org[j] != NF) continue;
t0 = umu(d1[i].x + e1[j].x , d1[i].y + e1[j].y);
t1 = umu(d1[i].x + e1[j].x * 2 , d1[i].y + e1[j].y * 2);
if(t0 != NF && t1 != NF) {
c1[i].org[j] = i;
c1[t0].org[j] = i;
c1[t1].org[j] = i;
k = 3;
t1 = umu(d1[i].x + e1[j].x * k , d1[i].y + e1[j].y * k);
while(t1 != NF) {
c1[t1].org[j] = i;
k++;
t1 = umu(d1[i].x + e1[j].x * k , d1[i].y + e1[j].y * k);
}
}
}
}
for(j = 0 ; j < N37 ; j++) {
MrPt2[0][j] = MrPt1[0][j]; /* 回 /*
MrPt2[1][j] = MrPt1[0][MrPt1[0][j]]; /* 回回 /*
MrPt2[2][j] = N36 - MrPt1[0][j]; /* 回 上 /*
MrPt2[3][j] = N36 - MrPt2[1][j]; /* 回回上 /*
MrPt2[4][j] = MrPt1[1][j]; /* 左 /*
MrPt2[5][j] = MrPt1[1][MrPt2[0][j]]; /* 回 左 /*
MrPt2[6][j] = MrPt1[1][MrPt2[1][j]]; /* 回回 左 /*
MrPt2[7][j] = MrPt1[1][MrPt2[2][j]]; /* 回 上左 /*
MrPt2[8][j] = MrPt1[1][MrPt2[3][j]]; /* 回回上左 /*
MrPt2[9][j] = N36 - j; /* 上 /*
MrPt2[10][j] = N36 - MrPt1[1][j]; /* 上左 /*
}
r1 = (int *)malloc(sizeof(int) * N37);
if(r1 == NULL) {
fprintf(stderr , "メモリ確保エラー\n");
exit(0);
}
}
/******************************************************************************
機 能：再帰関数
引 数：
n1 INT (I) 座標番号
n2 INT (I) 置いたコインの数
戻り値：なし
*****************************************************************************/*
void sub(int n1 , int n2)
{
int i;
int t;
if(n2 < max + n1 - N37) return;
if(n1 == N37) {
if(n2 > max) {
max = n2;
count = 0;
}
if(n2 == max) check();
return;
}
/* ここにコインを置けるかチェック /*
for(i = 0 ; i < N12 ; i++) {
t = c1[n1].org[i];
if(t == NF) continue;
if(c1[t].count[i] == N2) break;
}
/* 置けるなら、置いて次へ /*
if(i == N12) {
for(i = 0 ; i < N12 ; i++) {
t = c1[n1].org[i];
if(t == NF) continue;
c1[t].count[i]++;
}
f1[n1] = ON;
sub(n1 + 1 , n2 + 1);
f1[n1] = OFF;
for(i = 0 ; i < N12 ; i++) {
t = c1[n1].org[i];
if(t == NF) continue;
c1[t].count[i]--;
}
}
/* 高速化のため、鏡像などを事前に排除する。 /*
if(n1 == 3 && f1[0] == ON) return;
if(n1 == 15 && f1[0] == ON) return;
if(n1 == 15 && f1[3] == ON) return;
if(n1 == 21 && f1[0] == ON) return;
if(n1 == 33 && f1[0] == ON) return;
if(n1 == 36 && f1[0] == ON) return;
/* コインを置かずに次へ /*
sub(n1 + 1 , n2);
}
/******************************************************************************
機 能：メイン
引 数：なし
戻り値：常に１
*****************************************************************************/*
int main(void)
{
init();
sub(0 , 0);
free(r1);
printf("最大 %d 枚 、 %d 通り\n" , max , count);
return(0);
}
|
第122回（5月）III型素組数
|
|
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
int fUsed[1000]; /* 使用済みかどうかのフラグ OFF=未使用 ON=使用 /*
int nSoku[1000]; /* カレントのIII型素組数 /*
int nHozn[1000]; /* MAXのIII型素組数を保存しておく /*
int max = -1; /* 桁のMAX値 /*
int count = 0; /* 同じ桁の個数 /*
int nSosu[100][3]; /* 素数 /*
int nDigt[100][3]; /* 素数の１の位 /*
int aSosu[100]; /* 素数の数 /*
/* ============================================================================
機能 : 初期化処理（あらかじめ素数を求める）
引数 : なし
戻り値 : なし
============================================================================ /*
void init(void)
{
int fSosu , i , j , t;
for(i = 10 ; i < 100 ; i++) aSosu[i] = 0;
for(i = 101 ; i < 1000 ; i+=2) {
fUsed[i] = OFF; /* 初期状態は全て未使用にする /*
fSosu = ON;
for(j = 2 ; j < 32 ; j++) {
if((i % j) == 0) {
fSosu = OFF; /* 約数があれば、非素数 /*
break;
}
}
if(fSosu == ON) { /* 素数なら登録する /*
t = i / 10;
nSosu[t][aSosu[t]] = i;
nDigt[t][aSosu[t]] = i % 10;
aSosu[t]++;
}
}
}
/* ============================================================================
機能 : 再帰ルーチン
引数 : (1) int n (I) 現在の桁数
(2) int m (I) 前２桁の数（１１〜９９）
戻り値 : なし
============================================================================ /*
void sub(int n , int m)
{
int i , n1 , s , t;
if(n == max) { /* 最大桁と同じなら、保存＆カウントアップ /*
for(i = 0 ; i < n ; i++) nHozn[i] = nSoku[i];
count++;
}
else if(n > max) { /* 最大桁更新 /*
for(i = 0 ; i < n ; i++) nHozn[i] = nSoku[i];
count = 1;
max = n;
}
n1 = n + 1;
t = nSoku[n - 1] * 10;
for(i = 0 ; i < aSosu[m] ; i++) {
s = nSosu[m][i];
if(fUsed[s] == ON) continue; /* 使用済みならスキップ /*
nSoku[n] = nDigt[m][i];
fUsed[s] = ON; /* その素数を使用済みにする /*
sub(n1 , t + nSoku[n]);
fUsed[s] = OFF; /* その素数を未使用に戻す /*
}
}
/* ============================================================================
機能 : メイン
引数 : なし
戻り値 : 常に1
============================================================================ /*
int main(void)
{
int i , j , t;
init();
for(i = 1 ; i < 10 ; i++) { /* 最上位桁 /*
nSoku[0] = i;
t = i * 10;
for(j = 1 ; j < 10 ; j++) { /* ２番目の桁 /*
nSoku[1] = j;
sub(2 , t + j);
}
}
for(i = 0 ; i < max ; i++) printf("%d" , nHozn[i]);
printf("\n");
printf("個数 %d\n" , count);
return(0);
}
|
第120回（3月）素性のよい数たち
|
|
#include <stdio.h>
#include <stdlib.h>
#define OFF 0
#define ON 1
int check(int n)
{
int k = 5;
if((n % 3) == 0) return(OFF);
while(1) {
if(k * k > n) return(ON);
if((n % k) == 0) return(OFF);
if((n % (k + 2)) == 0) return(OFF);
k += 6;
}
}
int sub1(int n)
{
int i0 , i1 , i2 , i3 , i4 , i5 , i6 , i7;
int n1 , n2 , n3 , n4 , n5 , n6;
int s;
for(i0 = 2 ; i0 < n ; i0++) {
n1 = n - i0;
for(i1 = 1 ; i1 < n1 ; i1 += 2) {
n2 = n1 - i1;
for(i2 = i1 + 2 ; i2 < n2 ; i2 += 2) {
n3 = n2 - i2;
for(i3 = i2 + 2 ; i3 < n3 ; i3 += 2) {
n4 = n3 - i3;
for(i4 = i3 + 2 ; i4 < n4 ; i4 += 2) {
n5 = n4 - i4;
for(i5 = i4 + 2 ; i5 < n5 ; i5 += 2) {
n6 = n5 - i5;
for(i6 = i5 + 2 ; i6 < n6 ; i6 += 2) {
i7 = n6 - i6;
if(i7 <= i6) continue;
s = i1 * i2 * i3 * i4 * i5 * i6 * i7 + i0;
if(check(s) == OFF) continue;
s = i0 * i2 * i3 * i4 * i5 * i6 * i7 + i1;
if(check(s) == OFF) continue;
s = i0 * i1 * i3 * i4 * i5 * i6 * i7 + i2;
if(check(s) == OFF) continue;
s = i0 * i1 * i2 * i4 * i5 * i6 * i7 + i3;
if(check(s) == OFF) continue;
s = i0 * i1 * i2 * i3 * i5 * i6 * i7 + i4;
if(check(s) == OFF) continue;
s = i0 * i1 * i2 * i3 * i4 * i6 * i7 + i5;
if(check(s) == OFF) continue;
s = i0 * i1 * i2 * i3 * i4 * i5 * i7 + i6;
if(check(s) == OFF) continue;
s = i0 * i1 * i2 * i3 * i4 * i5 * i6 + i7;
if(check(s) == ON) {
printf("%d %d %d %d %d %d %d %d\n" ,
i0 , i1 , i2 , i3 , i4 , i5 , i6 , i7);
return(ON);
}
}
}
}
}
}
}
}
return(OFF);
}
int main(int argc , char **argv)
{
int n = 1 + 2 + 3 + 5 + 7 + 9 + 11 + 13;
if(argc != 1) {
fprintf(stderr , "Usage : %s\n" , argv[0]);
exit(0);
}
while(sub1(n) == OFF) {
n += 2;
}
return(0);
}
|
第119回（2月）Ｈ２Ｏ
|
|
#include <stdio.h>
#define OFF 0
#define ON 1
#define NX 4 /* 横方向の数 /*
#define NX1 3 /* NX - 1 /*
#define NY 3 /* 縦方向の数 /*
#define NY1 2 /* NY - 1 /*
#define NXY 12 /* NX * NY /*
#define N0 0 /* 0オリジン /*
#define N1 4096 /* 2^12 /*
#define N2 144 /* ４×３平面にコインを８個置くパターンの数（鏡像除く） /*
#define N3 2048 /* 2^11 /*
int nxt[N1][32]; /* 次のパターン /*
int nnxt[N1]; /* 次のパターンの数 /*
int c3[N1]; /* そのパターンにたどり着く最小手 /*
static int d1[][NX] = { ON,OFF,OFF,ON,ON,ON,ON,ON,ON,OFF,OFF,ON };
static int d2[][NX] = { ON,ON,ON,OFF,ON,OFF,ON,OFF,ON,ON,ON,OFF };
int e1; /* 終了パターン(O) /*
int min = N2;
int r2[N2]; /* たどったパターン（最小手） /*
int f1[NY][NX]; /* ２個接する可能性の数 /*
int f2[NY][NX][4][4]; /* ２個接する座標 /*
/* コイン表示 /*
void disp(int r)
{
int x , y;
int g1 = N3;
printf("−−−−\n");
for(y = N0 ; y < NY ; y++) {
for(x = N0 ; x < NX ; x++) {
if(r >= g1) {
printf("〇");
r -= g1;
}
else printf(" ");
g1 /= 2;
}
printf("\n");
}
}
/* パターンの番号を求める /*
int calc(int b1[][NX])
{
int x , y;
int s0 = 0 , s1 = 0 , s2=0 , s3 = 0;
int g1 = 1;
for(y = N0 ; y < NY ; y++) {
for(x = N0 ; x < NX ; x++) {
if(b1[y][x] == 1) s0 += g1;
if(b1[NY1 - y][x] == 1) s1 += g1;
if(b1[y][NX1 - x] == 1) s2 += g1;
if(b1[NY1 - y][NX1 - x] == 1) s3 += g1;
g1 += g1;
}
}
if(s1 < s0) s0 = s1;
if(s2 < s0) s0 = s2;
if(s3 < s0) s0 = s3;
return(s0);
}
int check(int b1[][NX] , int x1 , int y1 , int x2 , int y2)
{
int i;
/* 囲まれているかどうかのチェック /*
if(b1[0][1] == ON && b1[0][2] == ON && b1[1][3] == ON &&
b1[2][2] == ON && b1[2][1] == ON && b1[1][0] == ON) {
if(x1 == 1 && y1 == 1 && (x2 != 2 || y2 != 1)) return(OFF);
if(x1 == 2 && y1 == 1 && (x2 != 1 || y2 != 1)) return(OFF);
if(x2 == 1 && y2 == 1 && (x1 != 2 || y1 != 1)) return(OFF);
if(x2 == 2 && y2 == 1 && (x1 != 1 || y1 != 1)) return(OFF);
}
if((x1 == 1 && y1 == 1) || (x2 == 1 && y2 == 1)) {
if(b1[2][1] == ON && b1[1][2] == ON &&
b1[0][1] == ON && b1[1][0] == ON) return(OFF);
}
if((x1 == 2 && y1 == 1) || (x2 == 2 && y2 == 1)) {
if(b1[2][2] == ON && b1[1][3] == ON &&
b1[0][2] == ON && b1[1][1] == ON) return(OFF);
}
/* 移動先で２個のコインに接するかどうかのチェック /*
for(i = 0 ; i < f1[y2][x2] ; i++) {
if(b1[f2[y2][x2][i][1]][f2[y2][x2][i][0]] == ON &&
b1[f2[y2][x2][i][3]][f2[y2][x2][i][2]] == ON) return(ON);
}
return(OFF);
}
/* 初期化処理 /*
void init(void)
{
int i0 , i1 , i2 , i3;
int b1[NY][NX];
int x1 , y1 , x2 , y2 , x3 , y3;
int i , k , n;
for(i0 = N0 ; i0 < N1 ; i0++) {
nnxt[i0] = 0;
c3[i0] = N2;
}
for(y1 = N0 ; y1 < NY ; y1++) {
for(x1 = 0 ; x1 < NX ; x1++) b1[y1][x1] = ON;
}
for(y1 = N0 ; y1 < NY ; y1++) {
for(x1 = N0 ; x1 < NX ; x1++) {
f1[y1][x1] = 0;
for(x2 = -1 ; x2 < 2 ; x2 += 2) {
for(y2 = -1 ; y2 < 2 ; y2 += 2) {
x3 = x1 + x2;
y3 = y1 + y2;
if(x3 >= N0 && x3 < NX && y3 >= N0 && y3 < NY) {
f2[y1][x1][f1[y1][x1]][0] = x3;
f2[y1][x1][f1[y1][x1]][1] = y1;
f2[y1][x1][f1[y1][x1]][2] = x1;
f2[y1][x1][f1[y1][x1]][3] = y3;
f1[y1][x1]++;
}
}
}
}
}
for(i0 = N0 ; i0 < 9 ; i0++) {
b1[i0 / NX][i0 % NX] = OFF;
for(i1 = i0 + 1 ; i1 < 10 ; i1++) {
b1[i1 / NX][i1 % NX] = OFF;
for(i2 = i1 + 1 ; i2 < 11 ; i2++) {
b1[i2 / NX][i2 % NX] = OFF;
for(i3 = i2 + 1 ; i3 < NXY ; i3++) {
b1[i3 / NX][i3 % NX] = OFF;
n = calc(b1);
if(nnxt[n] > 0) {
b1[i3 / NX][i3 % NX] = ON;
continue;
}
for(y1 = N0 ; y1 < NY ; y1++) {
for(x1 = N0 ; x1 < NX ; x1++) {
if(b1[y1][x1] == OFF) continue;
for(y2 = N0 ; y2 < NY ; y2++) {
for(x2 = N0 ; x2 < NX ; x2++) {
if(b1[y2][x2] == ON) continue;
b1[y1][x1] = OFF;
if(check(b1 , x1 , y1 , x2 , y2) == OFF) {
b1[y1][x1] = ON;
continue;
}
b1[y2][x2] = ON;
k = calc(b1);
for(i = 0 ; i < nnxt[n] ; i++) {
if(k == nxt[n][i]) break;
}
if(i == nnxt[n]) nxt[n][nnxt[n]++] = k;
b1[y2][x2] = OFF;
b1[y1][x1] = ON;
}
}
}
}
b1[i3 / NX][i3 % NX] = ON;
}
b1[i2 / NX][i2 % NX] = ON;
}
b1[i1 / NX][i1 % NX] = ON;
}
b1[i0 / NX][i0 % NX] = ON;
}
}
/* 再起的呼び出し関数 /*
void sub(int p1 , int count , int r1[])
{
int i;
int p2;
if(count > min) return;
if(p1 == e1) {
if(count < min) {
min = count;
for(i = 0 ; i < count ; i++) r2[i] = r1[i];
}
return;
}
for(i = 0 ; i < nnxt[p1] ; i++) {
p2 = nxt[p1][i];
if(count > c3[p2]) continue;
c3[p2] = count;
r1[count + 1] = p2;
sub(p2 , count + 1 , r1);
}
}
/* メイン /*
int main(void)
{
int i;
int s1; /* 初期パターン(H) /*
int r1[N2]; /* たどったパターン /*
init();
s1 = calc(d1);
e1 = calc(d2);
r1[0] = s1;
c3[s1] = 0;
sub(s1 , 0 , r1);
for(i = 0 ; i < min ; i++) { /* 結果表示 /*
disp(r2[i]);
}
disp(e1);
return(0);
}
|
第118回（1月）ウサギと犬
|
|
#include <stdio.h>
#include <stdlib.h>
#define N1 1320 /* パターンの数 /*
#define N2 11 /* 場所の数 /*
#define N3 4 /* 犬が勝つパターンの数 /*
#define N4 3 /* 犬の数 /*
#define N5 120 /* N1 / N2 /*
#define OFF 0
#define ON 1
#define MAKE -1 /* 犬の負け手順 /*
#ifdef UNIX
#define CLS "clear" /* 画面をクリアするコマンド（ＵＮＩＸ） /*
#else
#define CLS "cls" /* 画面をクリアするコマンド（ＭＳ−ＤＯＳ） /*
#endif
#define NON 0 /* 誰もいない /*
#define RAB 1 /* 兎がいる /*
#define DOG 2 /* 犬がいる /*
static int m1[N2][8] = {
1, 2, 3, 0, 0, 0, 0, 0,
0, 2, 4, 5, 0, 0, 0, 0,
0, 1, 3, 5, 0, 0, 0, 0,
0, 2, 5, 6, 0, 0, 0, 0,
1, 5, 7, 0, 0, 0, 0, 0,
1, 2, 3, 4, 6, 7 ,8 ,9,
3, 5, 9, 0, 0, 0, 0, 0,
4, 5, 8,10, 0, 0, 0, 0,
5, 7, 9,10, 0, 0, 0, 0,
5, 6, 8,10, 0, 0, 0, 0,
7, 8, 9, 0, 0, 0, 0, 0};
static int nm1[N2] = {3,4,4,4,3,8,3,4,4,4,3};
/* 犬が動ける先の定義 /*
static int m2[N2][5] = {
0, 0, 0, 0, 0,
0, 2, 0, 0, 0,
0, 1, 3, 0, 0,
0, 2, 0, 0, 0,
1, 5, 0, 0, 0,
1, 2, 3, 4, 6,
3, 5, 0, 0, 0,
4, 5, 8, 0, 0,
5, 7, 9, 0, 0,
5, 6, 8, 0, 0,
7, 8, 9, 0, 0};
static int nm2[N2] = {0,2,3,2,2,5,2,3,3,3,3};
typedef struct {
int r_pos; /* うさぎの場所 /*
int d_pos[N4]; /* 犬の場所 /*
int r_pat[8]; /* うさぎが動く場合の次のパターン番号 /*
int nr_pat; /* 上の通りの数 /*
int d_pat[9]; /* 犬が動く場合の次のパターン番号 /*
int nd_pat; /* 上の通りの数 /*
int d_sts; /* 犬の状態 ON=勝ち OFF=未定/*
int d_nxt; /* 犬の必勝手 MAKE=犬の負け/*
int r_sts; /* 兎の状態 ON= 負け OFF=未定 /*
} PAT;
PAT pat[N1];
/* 兎が動けなくなる（犬の勝利）パターン /*
static int w1[N3][N2] = {
1,2,2,2,0,0,0,0,0,0,0,
0,2,0,0,1,2,0,2,0,0,0,
0,0,0,2,0,2,1,0,0,2,0,
0,0,0,0,0,0,0,2,2,2,1};
int w2[N3];
int getN(int b[])
{
int q[N4]; /* 犬の場所 /*
int i , j , n = 0;
int r; /* 兎の場所 /*
for(i = 0 ; i < N2 ; i++) {
if(b[i] == RAB) r = i;
else if(b[i] == DOG) q[n++] = i;
}
r *= N5;
for(i = r ; i < N1 ; i++) {
for(j = 0 ; j < N4 ; j++) {
if(pat[i].d_pos[j] != q[j]) break;
}
if(j == N4) return(i);
}
fprintf(stderr , "初期化処理プログラムエラー\n");
exit(0);
}
/* 犬の次の手を求める /*
int calc(void)
{
/* 兎が動ける先の定義 /*
int i , j;
int count = 0;
for(i = 0 ; i < N1 ; i++) {
if(pat[i].d_sts == ON) continue;
for(j = 0 ; j < pat[i].nd_pat ; j++) {
if(pat[pat[i].d_pat[j]].r_sts == ON) {
pat[i].d_sts = ON;
pat[i].d_nxt = pat[i].d_pat[j];
count++;
break;
}
}
}
if(count == 0) return(0);
for(i = 0 ; i < N1 ; i++) {
if(pat[i].r_sts == ON) continue;
for(j = 0 ; j < pat[i].nr_pat ; j++) {
if(pat[pat[i].r_pat[j]].d_sts == OFF) break;
}
if(j == pat[i].nr_pat) {
pat[i].r_sts = ON;
count++;
}
}
return(count);
}
/* 初期化処理 /*
void init(void)
{
int n = 0;
int i0 , i1 , i2 , i3;
int t0 , t1;
int b[N2];
for(i0 = 0 ; i0 < N2 ; i0++) {
for(i1 = 0 ; i1 < 9 ; i1++) {
if(i0 == i1) continue;
for(i2 = i1 + 1 ; i2 < 10 ; i2++) {
if(i0 == i2) continue;
for(i3 = i2 + 1 ; i3 < N2 ; i3++) {
if(i0 == i3) continue;
pat[n].r_pos = i0;
pat[n].d_pos[0] = i1;
pat[n].d_pos[1] = i2;
pat[n].d_pos[2] = i3;
n++;
}
}
}
}
for(i0 = 0 ; i0 < N1 ; i0++) {
for(i1 = 0 ; i1 < N2 ; i1++) b[i1] = NON;
b[pat[i0].r_pos] = RAB;
for(i1 = 0 ; i1 < N4 ; i1++) b[pat[i0].d_pos[i1]] = DOG;
pat[i0].nr_pat = pat[i0].nd_pat = 0;
t0 = pat[i0].r_pos;
for(i1 = 0 ; i1 < nm1[t0] ; i1++) {
t1 = m1[t0][i1];
if(b[t1] != NON) continue;
b[t0] = NON;
b[t1] = RAB;
n = getN(b);
pat[i0].r_pat[pat[i0].nr_pat++] = n;
b[t0] = RAB;
b[t1] = NON;
}
for(i1 = 0 ; i1 < N4 ; i1++) {
t0 = pat[i0].d_pos[i1];
for(i2 = 0 ; i2 < nm2[t0] ; i2++) {
t1 = m2[t0][i2];
if(b[t1] != NON) continue;
b[t0] = NON;
b[t1] = DOG;
n = getN(b);
pat[i0].d_pat[pat[i0].nd_pat++] = n;
b[t0] = DOG;
b[t1] = NON;
}
}
}
for(i0 = 0 ; i0 < N1 ; i0++) {
pat[i0].d_sts = OFF;
pat[i0].d_nxt = MAKE;
pat[i0].r_sts = OFF;
}
for(i0 = 0 ; i0 < N3 ; i0++) {
w2[i0] = getN(w1[i0]);
pat[w2[i0]].r_sts = ON;
}
while(1) {
if(calc() == 0) break;
}
}
/* ゲーム /*
void game(void)
{
int j;
int b[N2];
char p1[80];
int p; /* 兎の次の場所 /*
int p_old = -1; /* 兎の前の場所 /*
int n = -1;
static char *g1[] = {"" , "兎" , "犬"};
for(j = 0 ; j < N2 ; j++) b[j] = 0;
b[7] = b[9] = b[10] = DOG;
while(1) {
while(1) {
system(CLS);
if(b[0] == 0) printf(" Ａ\n");
else printf(" %s\n" , g1[b[0]]);
printf(" ／｜＼\n");
if(b[1] == 0) printf("Ｂ−");
else printf("%s−" , g1[b[1]]);
if(b[2] == 0) printf("Ｃ−");
else printf("%s−" , g1[b[2]]);
if(b[3] == 0) printf("Ｄ\n");
else printf("%s\n" , g1[b[3]]);
printf("｜＼｜／｜\n");
if(b[4] == 0) printf("Ｅ−");
else printf("%s−" , g1[b[4]]);
if(b[5] == 0) printf("Ｆ−");
else printf("%s−" , g1[b[5]]);
if(b[6] == 0) printf("Ｇ\n");
else printf("%s\n" , g1[b[6]]);
printf("｜／｜＼｜\n");
if(b[7] == 0) printf("Ｈ−");
else printf("%s−" , g1[b[7]]);
if(b[8] == 0) printf("Ｉ−");
else printf("%s−" , g1[b[8]]);
if(b[9] == 0) printf("Ｊ\n");
else printf("%s\n" , g1[b[9]]);
printf(" ＼｜／\n");
if(b[10] == 0) printf(" Ｋ\n");
else printf(" %s\n" , g1[b[10]]);
for(j = 0 ; j < N3 ; j++) {
if(n == w2[j]) {
printf("犬の勝ち\n");
return;
}
}
printf(">");
scanf("%s" , p1);
p = p1[0] - 'a';
if(p < 0 || p > 10) continue;
if(b[p] != NON) continue;
if(n == -1) break;
for(j = 0 ; j < nm1[p_old] ; j++) {
if(m1[p_old][j] == p) break;
}
if(j < nm1[p_old]) break;
}
if(p_old != -1) b[p_old] = NON;
b[p] = RAB;
n = pat[getN(b)].d_nxt;
if(n == MAKE) {
printf("うさぎの勝ち（プログラムエラー）\n");
return;
}
for(j = 0 ; j < N2 ; j++) b[j] = NON;
b[pat[n].r_pos] = RAB;
for(j = 0 ; j < N4 ; j++) b[pat[n].d_pos[j]] = DOG;
p_old = p;
}
}
int main(void)
{
init();
game();
}
| | | | | | | | | |