/******************************************************************************
Ｃマガジン（２００４年８月）電脳クラブ出題（年子平方数）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define N0 0 /* 基準の０ /*
#define N1 1 /* 単位の数 /*
#define N2 2 /* N1 + N1 /*
#define N3 3 /* 平方数の元の数のロング数の桁数 /*
#define N5 5 /* 平方数のロング数の桁数 /*
#define N9 9 /* N10 - 1 /*
#define N10 10 /* 32bitで表現できる桁数 /*
#define N20 20 /* 平方数表示文字数の最大値 /*
#define N21 21 /* 求める解の数 /*
#define K0 N0 /* ０ /*
#define K1 1 /* NO + N1 = 1 /*
#define K2 2 /* K1 + N1 = 2 /*
#define K3 3 /* K2 + N1 = 3 /*
#define K4 4 /* K3 + N1 = 4 /*
#define K5 5 /* K4 + N1 = 5 /*
#define K6 6 /* K5 + N1 = 6 /*
#define K7 7 /* K6 + N1 = 7 /*
#define K8 8 /* K7 + N1 = 8 /*
#define K9 9 /* K8 + N1 = 9 /*
#define M1 10 /* １０進数の１０ /*
#define M2 100 /* M1 * M1 /*
#define M3 1000 /* M2 * M1 /*
#define M4 10000 /* ロング数の最大値＋１ /*
#define M5 100000 /* M4 * M1 /*
#define M7 10000000 /* M5 * M2 /*
#define M8 100000000 /* M4 * M4 /*
#define L21 21 /* N20 + N1(NULLターミネート分) /*
#define CSPACE ' ' /* スペース /*
#define CZERO '0' /* ゼロ /*
#define FORM1 "%4d%4d%4d%4d%4d" /* ロング数→文字列用書式 /*
#define FORM2 "%2d %10d %20s\n" /* 解答表示用書式 /*
int count = 0; /* 正解の数（２１まで） /*
/******************************************************************************
機能：ロング数を２乗する。 a1 = b1 * b1
引数：
(1) a1 : ２乗後の数(ロング数)
(2) b1 : ２乗される数（通常数）
戻り値：なし
*****************************************************************************/*
void multi(int a1[] , int b1)
{
int i , j; /* ループの制御変数 /*
int b2[N3]; /* ２乗される数のロング数 /*
b2[N2] = b1 / M8; /* ２乗される数をロング数に変換する。一億、十億の位 /*
b2[N1] = (b1 / M4) % M4; /* 万〜千万の位 /*
b2[N0] = b1 % M4; /* 一〜千の位 /*
for(i = N0 ; i < N5 ; i++) a1[i] = N0; /* 初期化 /*
for(i = N0 ; i < N3 ; i++) {
for(j = N0 ; j < N3 ; j++) {
a1[i + j] += b2[i] * b2[j]; /* 各桁ごとの掛け算 /*
}
}
for(i = N0 ; i < N5 - N1 ; i++) {
a1[i + N1] += a1[i] / M4; /* 桁あふれ処理 /*
a1[i] %= M4;
}
}
/******************************************************************************
機能：平方数を求め、題意に合うかチェックし、合うなら表示する。
引数：
(1) i : ２乗される前の数
(2) m1 : iの桁数
戻り値：なし
*****************************************************************************/*
void sub(int i , int m1)
{
int j; /* ループの制御変数 /*
int a1[N5]; /* 平方数のロング数 /*
int n1 , n2; /* 平方数の左半分、右半分 /*
int f1 = OFF; /* ゼロサプレス用フラグ OFF:数字未登場、ON:登場済み/*
char buf[L21]; /* 平方数表示用 /*
multi(a1 , i); /* 平方数を求める /*
if (m1 == K1) { /* 平方前の数が１桁の場合 /*
n1 = a1[K0] / M1; /* 平方数の左側半分 /*
n2 = a1[K0] % M1; /* 平方数の右側半分 /*
}
else if(m1 == K2) { /* 同２桁の場合 /*
n1 = a1[K0] / M2; /* 平方数の左側半分 /*
n2 = a1[K0] % M2; /* 平方数の右側半分 /*
}
else if(m1 == K3) { /* 同３桁の場合 /*
n1 = a1[K1] * M1 + a1[K0] / M3; /* 平方数の左側半分 /*
n2 = a1[K0] % M3; /* 平方数の右側半分 /*
}
else if(m1 == K4) { /* 同４桁の場合 /*
n1 = a1[K1]; /* 平方数の左側半分 /*
n2 = a1[K0]; /* 平方数の右側半分 /*
}
else if(m1 == K5) { /* 同５桁の場合 /*
n1 = a1[K2] * M3 + a1[K1] / M1; /* 平方数の左側半分 /*
n2 = (a1[K1] % M1) * M4 + a1[K0]; /* 平方数の右側半分 /*
}
else if(m1 == K6) { /* 同６桁の場合 /*
n1 = a1[K2] * M2 + a1[K1] / M2; /* 平方数の左側半分 /*
n2 = (a1[K1] % M2) * M4 + a1[K0]; /* 平方数の右側半分 /*
}
else if(m1 == K7) { /* 同７桁の場合 /*
n1 = a1[K3] * M5 + a1[K2] * M1 + a1[K1] / M3; /* 平方数の左側半分 /*
n2 = (a1[K1] % M3) * M4 + a1[K0]; /* 平方数の右側半分 /*
}
else if(m1 == K8) { /* 同８桁の場合 /*
n1 = a1[K3] * M4 + a1[K2]; /* 平方数の左側半分 /*
n2 = a1[K1] * M4 + a1[K0]; /* 平方数の右側半分 /*
}
else if(m1 == K9) { /* 同９桁の場合 /*
n1 = a1[K4] * M7 + a1[K3] * M3 + a1[K2] / M1; /* 平方数の左側半分 /*
n2 = (a1[K2] % M1) * M8 + a1[K1] * M4 + a1[K0]; /* 平方数の右側半分 /*
}
if(n1 + N1 != n2 && n1 != n2 + N1) return; /* ±１チェック /*
count++;
sprintf(buf , FORM1 , a1[K4] , a1[K3] , a1[K2] , a1[K1] , a1[K0]);
for(j = N0 ; j < N20 ; j++) { /* 平方数の先行ゼロサプレス /*
if(f1 == OFF) { /* 数字未登場 /*
if (buf[j] == CZERO) buf[j] = CSPACE;
else if(buf[j] != CSPACE) f1 = ON;
}
else { /* 数字登場済み /*
if(buf[j] == CSPACE) buf[j] = CZERO;
}
}
printf(FORM2 , count , i , buf); /* 解答表示 /*
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：EXIT_SUCCESS
*****************************************************************************/*
int main(void)
{
double d1; /* 3.16 ... = sqrt(10.0) /*
int s1; /* ２乗して偶数桁になる開始の数 /*
int i , j; /* ループの制御変数 /*
int z1 = N1; /* 1 , 10 , 100 , 1000 , ... /*
d1 = sqrt((double)M1);
for(i = N0 ; i < N9 ; i++) {
s1 = (int)(d1 * (double)z1) + N1; /* 開始の数を求める /*
z1 *= M1;
for(j = s1 ; j < z1 ; j++) {
sub(j , i + N1);
if(count == N21) break; /* ２１個もとまったら終了 /*
}
}
return(EXIT_SUCCESS);
}
/******************************************************************************
Ｃマガジン２００４年８月号電脳クラブ出題（偶数桁の回文平方数）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define N0 0 /* 基準の０ /*
#define N1 1 /* 単位の数 /*
#define N2 2 /* N1 + N1 /*
#define N3 3 /* 平方数の元の数のロング数の桁数 /*
#define N6 6 /* 平方数のロング数の桁数 /*
#define N9 9 /* N10 - 1 /*
#define N10 10 /* 32bitで表現できる桁数 /*
#define N24 24 /* 平方数表示文字数の最大値 /*
#define N4 4 /* 求める解の数 /*
#define M0 1 /* = N1 /*
#define M1 10 /* １０進数の１０ /*
#define M2 100 /* M1 * M1 /*
#define M3 1000 /* M2 * M1 /*
#define M4 10000 /* ロング数の最大値＋１ /*
#define KETA04 4 /* ロング数の桁数 /*
#define L25 25 /* N20 + N1(NULLターミネート分) /*
#define CSPACE ' ' /* スペース /*
#define CZERO '0' /* ゼロ /*
typedef struct {
int idx; /* 索引 /*
int val; /* 値 /*
} RIGHT;
int count = 0; /* 求まった解の数 /*
/******************************************************************************
機能：ロング数を２乗する。 a1 = b1 * b1
引数：
(1) a1 : ２乗後の数(ロング数)
(2) b1 : ２乗される数（通常数）
戻り値：なし
*****************************************************************************/*
void multi(int a1[N6] , int b2[N3])
{
int i , j;
for(i = N0 ; i < N6 ; i++) a1[i] = N0;
for(i = N0 ; i < N3 ; i++) {
for(j = N0 ; j < N3 ; j++) {
a1[i + j] += b2[i] * b2[j];
}
}
for(i = N0 ; i < N6 - N1 ; i++) { /* 桁あふれ処理 /*
a1[i + N1] += a1[i] / M4;
a1[i] %= M4;
}
}
/******************************************************************************
機能：平方して、回文がどうかチェックする。
引数：
(1) b1 :平方前の数（ロング数）
(2) m1 : 平方前の桁数
戻り値：なし
*****************************************************************************/*
void sub(int b1[] , int m1)
{
int j , n = N0;
int a1[N6]; /* 平方数用ロング数 /*
int f1 = OFF;
char buf[L25]; /* 平方数表示用 /*
static int p1[] = {M0 , M1 , M2 , M3}; /* ロング数から１桁得る /*
int j2;
multi(a1 , b1);
for(j = 0 ; j < m1 ; j++) { /* 回文かどうかのチェック /*
j2 = m1 * 2 - j - 1;
if((a1[j / KETA04] / p1[j % KETA04]) % M1
!= (a1[j2 / KETA04] / p1[j2 % KETA04]) % M1) return;
}
count++;
printf("%2d " , count);
sprintf(buf , "%4d%4d%4d" , b1[2] , b1[1] , b1[0]);
for(j = N0 ; j < 12 ; j++) { /* 平方数の先行ゼロサプレス /*
if(f1 == OFF) { /* 数字未登場 /*
if (buf[j] == CZERO) buf[j] = CSPACE;
else if(buf[j] != CSPACE) f1 = ON;
}
else { /* 数字登場済み /*
if(buf[j] == CSPACE) buf[j] = CZERO;
}
}
printf("%12s " , buf);
f1 = OFF;
sprintf(buf , "%4d%4d%4d%4d%4d%4d" ,
a1[5] , a1[4] , a1[3] , a1[2] , a1[1] , a1[0]);
for(j = N0 ; j < N24 ; j++) { /* 平方数の先行ゼロサプレス /*
if(f1 == OFF) { /* 数字未登場 /*
if (buf[j] == CZERO) buf[j] = CSPACE;
else if(buf[j] != CSPACE) f1 = ON;
}
else { /* 数字登場済み /*
if(buf[j] == CSPACE) buf[j] = CZERO;
}
}
printf("%24s\n" , buf);
}
/******************************************************************************
機能：上位、下位から平方前のロング数を組み立てる。
引数：
(1) joi : 上位の桁（２〜４桁）
(2) kai : 下位の桁（２〜４桁）
(3) m1 : 平方前の桁数
戻り値：
*****************************************************************************/*
void makeLong(int joi , int kai , int m1)
{
int i; /* ループ制御変数 /*
int b1[N3]; /* ２乗前の数 /*
b1[0] = kai;
b1[2] = N0;
if (m1 <= 4) { /* ２、３、４桁 /*
if(joi != kai) return;
b1[1] = N0;
sub(b1 , m1);
}
else if(m1 == 5) { /* ５桁 /*
if(joi % M1 != kai / M2) return;
b1[0] += ((joi / M1) % M1) * M3;
b1[1] = joi / M2;
sub(b1 , m1);
}
else if(m1 == 6) { /* ６桁 /*
b1[0] += (joi % M1) * M3;
b1[1] = joi / M1;
sub(b1 , m1);
}
else if(m1 == 7) { /* ７桁 /*
if(joi % 10 != kai / M3) return;
b1[1] = joi / M1;
sub(b1 , m1);
}
else if(m1 == 8) { /* ８桁 /*
b1[1] = joi;
sub(b1 , m1);
}
else if(m1 == 9) { /* ９桁 /*
b1[1] = (joi % M3) * M1;
b1[2] = joi / M3;
for(i = N0 ; i < M1 ; i++) { /* 上位と下位の間の数 /*
b1[1]++;
sub(b1 , m1);
if(count == N4) return; /* 答えが４個求まった /*
}
}
else if(m1 == 10) { /* １０桁 /*
b1[1] = (joi % M2) * M2;
b1[2] = joi / M2;
for(i = N0 ; i < M2 ; i++) { /* 上位と下位の間の数 /*
b1[1]++;
sub(b1 , m1);
if(count == N4) return; /* 答えが４個求まった /*
}
}
else if(m1 == 11) { /* １１桁 /*
b1[1] = (joi % M1) * M3;
b1[2] = joi / M1;
for(i = N0 ; i < M3 ; i++) { /* 上位と下位の間の数 /*
b1[1]++;
sub(b1 , m1);
if(count == N4) return; /* 答えが４個求まった /*
}
}
else if(m1 == 12) { /* １２桁 /*
b1[1] = N0;
b1[2] = joi;
for(i = N0 ; i < M4 ; i++) { /* 上位と下位の間の数 /*
b1[1]++;
sub(b1 , m1);
if(count == N4) return; /* 答えが４個求まった /*
}
}
}
/******************************************************************************
機能：ｑｓｏｒｔ用ｃｍｐ関数
引数：ａ，ｂ
戻り値：-1,0,1
*****************************************************************************/*
int cmp(const void *a , const void *b)
{
RIGHT *za , *zb;
za = (RIGHT *)a;
zb = (RIGHT *)b;
if (za->val < zb->val) return(-1);
else if(za->val == zb->val) return(0);
else return(1);
}
/******************************************************************************
機能：メイン補助
引数：なし
戻り値：なし
*****************************************************************************/*
void main2(void)
{
int i0 , i1 , i2 , i3; /* ループ制御変数 /*
int min , max; /* ２乗後の最小、最大 /*
RIGHT right[M4]; /* ２乗後の右半分 /*
int rev; /* ２乗後の左側の反転＝右側 /*
double d1; /* sqrt(10.0) = 3.16... /*
int s1;
int t2 , t3;
d1 = sqrt((double)M1);
/* ２桁（２乗前）→４桁（平方数） /*
for(i1 = N0 ; i1 < M2 ; i1++) {
right[i1].idx = i1;
right[i1].val = (i1 * i1) % M2;
}
qsort((void *)right , M2 , sizeof(RIGHT) , cmp);
s1 = (int)(d1 * (double)M1);
for(i1 = s1 ; i1 < M2 ; i1++) {
min = i1 * i1 / M2; /* ２乗後の左半分最小値 /*
max = (i1 + 1) * (i1 + 1) / M2; /* ２乗後の左半分最大値 /*
for(i2 = min ; i2 <= max ; i2++) {
rev = i2 / M1 + (i2 % M1) * M1;
t2 = N0;
t3 = M2 / 2;
while(t3 > N0) { /* ２分岐探査 /*
if(right[t2 + t3].val < rev) t2 += t3;
t3 /= 2;
}
for(i3 = N0 ; i3 < M2 ; i3++) {
if(rev == right[i3].val) makeLong(i1 , right[i3].idx , 2);
if(right[i3].val > rev) break;
if(count == N4) return; /* 答えが４個求まった /*
}
}
}
/* ３桁〜６桁→６桁〜１２桁（平方数） /*
for(i1 = N0 ; i1 < M3 ; i1++) {
right[i1].idx = i1;
right[i1].val = (i1 * i1) % M3;
}
qsort((void *)right , M3 , sizeof(RIGHT) , cmp);
s1 = (int)(d1 * (double)M2);
for(i0 = 3 ; i0 < 7 ; i0++) {
for(i1 = s1 ; i1 < M3 ; i1++) {
min = i1 * i1 / M3; /* ２乗後の左半分最小値 /*
max = (i1 + N1) * (i1 + N1) / M3; /* ２乗後の左半分最大値 /*
for(i2 = min ; i2 <= max ; i2++) {
rev = i2 / M2 + ((i2 / M1) % M1) * M1 + (i2 % M1) * M2;
t2 = N0;
t3 = M3 / 2;
while(t3 > 0) { /* ２分岐探査 /*
if(right[t2 + t3].val < rev) t2 += t3;
t3 /= 2;
}
for(i3 = t2 ; i3 < M3 ; i3++) {
if(rev == right[i3].val) makeLong(i1 , right[i3].idx , i0);
if(right[i3].val > rev) break;
if(count == N4) return; /* 答えが４個求まった /*
}
}
}
}
/* ７桁〜１２桁→１４桁〜２４桁（平方数） /*
for(i1 = N0 ; i1 < M4 ; i1++) {
right[i1].idx = i1;
right[i1].val = (i1 * i1) % M4;
}
qsort((void *)right , M4 , sizeof(RIGHT) , cmp);
s1 = (int)(d1 * (double)M3);
for(i0 = 7 ; i0 < 13 ; i0++) {
for(i1 = s1 ; i1 < M4 ; i1++) {
min = i1 * i1 / M4; /* ２乗後の左半分最小値 /*
max = (i1 + N1) * (i1 + N1) / M4; /* ２乗後の左半分最大値 /*
for(i2 = min ; i2 <= max ; i2++) {
rev = i2 / M3 + ((i2 / M2) % M1) * M1 + ((i2 / M1) % M1) * M2
+ (i2 % M1) * M3;
t2 = N0;
t3 = M4 / 2;
while(t3 > N0) { /* ２分岐探査 /*
if(right[t2 + t3].val < rev) t2 += t3;
t3 /= 2;
}
for(i3 = t2 ; i3 < M4 ; i3++) {
if(rev == right[i3].val) makeLong(i1 , right[i3].idx , i0);
if(right[i3].val > rev) break;
if(count == N4) return; /* 答えが４個求まった /*
}
}
}
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：EXIT_SUCCESS
*****************************************************************************/*
int main(void)
{
main2();
return(EXIT_SUCCESS);
}
|
第162回（9月）切手切って乗りきって
|
|
/******************************************************************************
Ｃマガジン２００４年６月号出題（切手切って乗りきって）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define Z3 3 /* 分割後の切手片の１辺の長さ /*
#define Z4 4 /* 分割後の切手片の１辺の長さ /*
#define Z5 5 /* 分割前の切手片の１辺の長さ /*
#define Z7 7 /* Z4 * 2 - N1 中心から正負それぞれに向かうためこの値となる /*
#define N9 9 /* 分割後の切手片の切手枚数 /*
#define N0 0 /* 基準値 /*
#define N1 1 /* 最小の単位 /*
#define N2 2 /* N1 + N1 /*
#define N10 10 /* N9 + N1 /*
#define N16 16 /* 分割後の切手片の切手枚数 /*
#define N17 17 /* N16 * N1 /*
#define M0 0 /* 鏡像チェックで使用する。xに対する索引値 /*
#define M1 1 /* 鏡像チェックで使用する。(Z4 - x)に対する索引値 /*
#define M2 2 /* 鏡像チェックで使用する。yに対する索引値 /*
#define M3 3 /* 鏡像チェックで使用する。(Z4 - y)に対する索引値 /*
#define NP1 1 /* 分割後の片を構成する片の最小数 /*
#define NP2 2 /* 分割後の片を構成する片の数（両者が同じ場合） /*
#define NP3 3 /* 分割後の片を構成する片の最大数 /*
#define NP4 4 /* 分割前の片の数 /*
#define ID3 0 /* ３×３を識別するＩＤ /*
#define ID4 1 /* ４×４を識別するＩＤ /*
#define NON - N1 /* そこに切手がない状態 /*
typedef struct {
int x; /* Ｘ座標 /*
int y; /* Ｙ座標 /*
} XY; /* ＸＹ座標 /*
typedef struct {
int ban[Z4][Z4]; /* 切手 /*
XY xy[N16]; /* 切手がある座標 /*
} PIECE; /* 切手片定義の構造体 /*
typedef struct {
int ban[Z5][Z5]; /* /*
} BAN5; /* 既出正解パターン /*
typedef struct {
int n; /* 片を構成する切手枚数 /*
int j; /* その中の順番 /*
} CUTPIECE;
PIECE *piece[N2][N17]; /* 切手片（全データ） /*
int nPiece[2][N17]; /* 枚数ごとの切手片の種類数 /*
BAN5 *ban5; /* 正解パターン /*
int nBan5 = N0; /* 正解数 /*
int nH4[N2]; /* ３×３、４×４の各使用片数 /*
int fCheck; /* 分割後に正方形になるかどうかのフラグ /*
static int len[] = {Z3 , Z4}; /* 分割後の辺の長さ /*
static int len2[] = {Z5 , Z7}; /* len[] * N2 - N1 /*
static int len3[] = {N9 , N16}; /* len[] * len[] /*
/******************************************************************************
機能：３×３、４×４全ての片を求める再帰処理
既出パターンかチェックし、新規パターンなら登録する
引数：
(1) ban 切手を置く盤
(2) n 置いた切手の枚数
(3) id ３×３、４×４を識別するＩＤ（ID3:３×３、ID4:４×４）
戻り値：なし
*****************************************************************************/*
void initSub(int ban[Z7][Z7] , int n , int id)
{
int x , y; /* 座標 /*
int i; /* ループの制御変数 /*
int xmin = Z7 , ymin = Z7 , xmax = - N1 , ymax = - N1;
/* 置いた切手の範囲 /*
int xz , yz = - N1; /* 置いた切手片の基準座標(Ｙ最小の中でＸ最小) /*
int t1 = N0;
int w1[Z7][Z7]; /* ワーク用盤 /*
for(y = N0 ; y < len2[id] ; y++) { /* 範囲を求める /*
for(x = N0 ; x < len2[id] ; x++) {
if(ban[y][x] == ON) {
if(x < xmin) xmin = x;
if(y < ymin) ymin = y;
if(x > xmax) xmax = x;
if(y > ymax) ymax = y;
}
}
}
if(xmax - xmin >= len[id]) return; /* 範囲を超えたら対象外 /*
if(ymax - ymin >= len[id]) return;
for(y = N0 ; y < len[id] ; y++) {
for(x = N0 ; x < len[id] ; x++) {
w1[y][x] = OFF;
}
}
for(y = N0 ; y < len2[id]; y++) {
for(x = N0 ; x < len2[id] ; x++) {
if(ban[y][x] == ON) {
w1[y - ymin][x - xmin] = ON; /* 原点方向へシフトする /*
if(yz == - N1) {
xz = x - xmin;
yz = y - ymin;
}
}
}
}
for(i = N0 ; i < nPiece[id][n] ; i++) { /* 既出パターンかチェックする /*
for(y = N0 ; y < len[id] ; y++) {
for(x = N0 ; x < len[id] ; x++) {
if(w1[y][x] != piece[id][n][i].ban[y][x]) break;
}
if(x < len[id]) break;
}
if(y == len[id]) return;
}
piece[id][n] = /* 新規パターン登録用のメモリ確保 /*
(PIECE *)realloc(piece[id][n] , sizeof(PIECE) * (nPiece[id][n] + N1));
if(piece[id][n] == NULL) {
fprintf(stderr , "realloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
for(y = N0 ; y < len[id] ; y++) { /* 盤の登録 /*
for(x = N0 ; x < len[id] ; x++) {
piece[id][n][nPiece[id][n]].ban[y][x] = w1[y][x];
if(w1[y][x] == ON) {
piece[id][n][nPiece[id][n]].xy[t1].x = x - xz;
piece[id][n][nPiece[id][n]].xy[t1++].y = y - yz;
}
}
}
nPiece[id][n]++;
if(n == len3[id]) return;
for(y = N0 ; y < len2[id] ; y++) { /* 座標の登録 /*
for(x = N0 ; x < len2[id] ; x++) {
if(ban[y][x] == ON) continue;
if((x > N0 && ban[y][x - N1] == ON) ||
(x < len2[id] - N1 && ban[y][x + N1] == ON) ||
(y > N0 && ban[y - N1][x] == ON) ||
(y < len2[id] - N1 && ban[y + N1][x] == ON)) {
ban[y][x] = ON;
initSub(ban , n + N1 , id);
ban[y][x] = OFF;
}
}
}
}
/******************************************************************************
機能：初期化
全ての３×３、４×４用の片を求める
引数：なし
戻り値：なし
*****************************************************************************/*
void init(void)
{
int i; /* ループの制御変数 /*
int ban[Z7][Z7]; /* 盤 /*
int x , y; /* 座標 /*
for(y = N0 ; y < Z7 ; y++) { /* 盤の初期化 /*
for(x = N0 ; x < Z7 ; x++) ban[y][x] = OFF;
}
for(i = N1 ; i <= N9 ; i++) nPiece[ID3][i] = N0; /* ３×３取得処理 /*
ban[Z3 - N1][Z3 - N1] = ON;
initSub(ban , N1 , ID3);
ban[Z3 - N1][Z3 - N1] = OFF;
for(i = N1 ; i <= N16 ; i++) nPiece[ID4][i] = N0; /* ４×４取得処理 /*
ban[Z4 - N1][Z4 - N1] = ON;
initSub(ban , N1 , ID4);
}
/******************************************************************************
機能：そこに切手片を置けるかどうかチェックし、置けるなら置く。
引数：
(1) ban : 切手片を置く盤
(2) x : 切手片を置く基準Ｘ座標
(3) y : 切手片を置く基準Ｙ座標
(4) i : 切手片の切手枚数
(5) j : 上記の中の一連番号
(6) id : ３×３、４×４を識別するＩＤ
(7) val : 設定する値
(8) size : 置く範囲
戻り値：OFF:置けない、ON:置ける
*****************************************************************************/*
int okeruka(int ban[Z5][Z5] , int x , int y , int i , int j , int id ,
int val , int size)
{
int k;
for(k = N0 ; k < i ; k++) {
if(x + piece[id][i][j].xy[k].x < N0) return(OFF); /* 盤の外 /*
if(x + piece[id][i][j].xy[k].x >= size) return(OFF);
if(y + piece[id][i][j].xy[k].y < N0) return(OFF);
if(y + piece[id][i][j].xy[k].y >= size) return(OFF);
if(ban[y + piece[id][i][j].xy[k].y][x + piece[id][i][j].xy[k].x] != NON)
return(OFF); /* 既に切手がある /*
}
for(k = N0 ; k < i ; k++) { /* 置く /*
ban[y + piece[id][i][j].xy[k].y][x + piece[id][i][j].xy[k].x] = val;
}
return(ON);
}
/******************************************************************************
機能：切手片を取り除く
引数：
(1) ban : 切手片を置く盤
(2) x : 切手片を置く基準Ｘ座標
(3) y : 切手片を置く基準Ｙ座標
(4) i : 切手片の切手枚数
(5) j : 上記の中の一連番号
(6) id : ３×３、４×４を識別するＩＤ
戻り値：なし
*****************************************************************************/*
void toru(int ban[Z5][Z5] , int x , int y , int i , int j , int id)
{
int k; /* ループの制御変数 /*
for(k = N0 ; k < i ; k++) {
ban[y + piece[id][i][j].xy[k].y][x + piece[id][i][j].xy[k].x] = NON;
}
}
/******************************************************************************
機能：３×３、４×４の正方形を作れるかどうかチェックする再帰関数
引数：
(1) ban : 盤
(2) cutPiece : 使用する片
(3) fUsed : 使用済みフラグ
(4) x : Ｘ座標
(5) y : Ｙ座標
(6) nH : 片の数
(7) id : ３×３、４×４を識別するＩＤ
(8) n : 片の何番目か
戻り値：なし
*****************************************************************************/*
void checkSub(int ban[Z5][Z5] , CUTPIECE cutPiece[N2][NP3] , int fUsed[NP3] ,
int x , int y , int nH , int id , int n)
{
int x2 , y2; /* 座標 /*
int i; /* ループの制御変数 /*
if(y == len[id]) {
fCheck = ON;
return;
}
x2 = x + N1; /* 次の座標を求める /*
y2 = y;
if(x2 == len[id]) {
x2 = N0;
y2++;
}
if(ban[y][x] != NON) { /* 既に切手が置いてあった場合は次の座標へ /*
checkSub(ban , cutPiece , fUsed , x2 , y2 , nH , id , n);
return;
}
for(i = N0 ; i < nH ; i++) {
if(fUsed[i] == ON) continue; /* 使用済み /*
if(okeruka(ban , x , y , cutPiece[id][i].n , cutPiece[id][i].j , id ,
n , Z4) == OFF) continue;
fUsed[i] = ON;
checkSub(ban , cutPiece , fUsed , x2 , y2 , nH , id , n + N1);
fUsed[i] = OFF;
toru(ban , x , y , cutPiece[id][i].n , cutPiece[id][i].j , id);
}
}
/******************************************************************************
機能：選んだ片でそれぞれ３×３、４×４の正方形を作れるか
５×５が既出でないかどうかチェックする
引数：
(1) cutPiece : 使用する片
(2) ban : 盤
戻り値：OFF:駄目、ON:チェック結果ＯＫ
*****************************************************************************/*
int check(CUTPIECE cutPiece[N2][NP3] , int ban[Z5][Z5])
{
int i , j , k; /* ループの制御変数 /*
int x , y; /* 座標 /*
int fUsed[NP3]; /* 使用済みフラグ /*
int w2[Z5][Z5];
int t1[NP4];
int x2 , y2; /* 座標 /*
int y1[NP4][N2];
int nY1;
static XY xy[] = {M1,M2 , M0,M3 , M1,M3 , M2,M0 , M3,M0 , M2,M1 , M3,M1};
/* 座標変換パターン /*
for(i = N0 ; i < nH4[ID3] ; i++) fUsed[i] = OFF;
for(y = N0 ; y < Z3 ; y++) {
for(x = N0 ; x < Z3 ; x++) w2[y][x] = NON;
}
fCheck = OFF;
checkSub(w2 , cutPiece , fUsed , N0 , N0 , nH4[ID3] , ID3 , N0);
if(fCheck == OFF) return(OFF);
for(i = N0 ; i < nH4[ID4] ; i++) fUsed[i] = OFF;
for(y = N0 ; y < Z4 ; y++) {
for(x = N0 ; x < Z4 ; x++) w2[y][x] = NON;
}
fCheck = OFF;
checkSub(w2 , cutPiece , fUsed , N0 , N0 , nH4[ID4] , ID4 , N0);
if(fCheck == OFF) return(OFF);
for(i = N0 ; i < nBan5 ; i++) {
for(j = N0 ; j < sizeof(xy) / sizeof(XY) ; j++) {
for(y = N0 ; y < Z5 ; y++) {
t1[M2] = y; /* Ｙ座標そのまま /*
t1[M3] = Z5 - y - N1; /* Ｙ座標反転 /*
for(x = N0 ; x < Z5 ; x++) {
t1[M0] = x; /* Ｘ座標そのまま /*
t1[M1] = Z5 - x - N1; /* Ｘ座標反転 /*
w2[y][x] = ban5[i].ban[t1[xy[j].y]][t1[xy[j].x]];
}
}
nY1 = N0;
for(y2 = N0 ; y2 < Z5 ; y2++) {
for(x2 = N0 ; x2 < Z5 ; x2++) {
for(k = N0 ; k < nY1 ; k++) {
if(y1[k][N0] == ban[y2][x2] && y1[k][N1] == w2[y2][x2])
break;
}
if(k == nY1) {
if(nY1 == NP4) break;
y1[nY1][N0] = ban[y2][x2];
y1[nY1][N1] = w2[y2][x2];
nY1++;
}
}
if(x2 < Z5) break;
}
if(y2 == Z5) return(OFF);
}
}
ban5 = (BAN5 *)realloc(ban5 , sizeof(BAN5) * (nBan5 + N1));
if(ban5 == NULL) { /* メモリ確保エラー /*
free(piece);
fprintf(stderr , "realloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
for(y = N0 ; y < Z5 ; y++) {
for(x = N0 ; x < Z5 ; x++) ban5[nBan5].ban[y][x] = ban[y][x];
}
nBan5++;
return(ON);
}
/******************************************************************************
機能：５×５を埋めていく再帰関数
引数：
(1) ban : 盤
(2) x : Ｘ座標
(3) y : Ｙ座標
(4) usedNo : 切手枚数ごとの片の使用数
(5) cutPiece : 使用する片
(6) mH3 : ３×３の片の内の何番目か
(7) mH4 : ４×４の片の内の何番目か
(8) n : 何番目の片か
戻り値：なし
*****************************************************************************/*
void sub(int ban[Z5][Z5] , int x , int y , int usedNo[N2][N17] ,
CUTPIECE cutPiece[N2][NP3] , int mH3 , int mH4 , int n)
{
int x2 , y2; /* 座標 /*
int i , j; /* ループの制御変数 /*
static char *stamp[] = {"□" , "■" , "○" , "●"}; /* 正解例表示用 /*
if(y == Z5) { /* ５×５を全て埋めた場合 /*
if(check(cutPiece , ban) == ON) {
for(y2 = N0 ; y2 < Z5 ; y2++) { /* 正解例表示 /*
for(x2 = N0 ; x2 < Z5 ; x2++)
printf("%s" , stamp[ban[y2][x2]]);
printf("\n");
}
printf("\n");
}
return;
}
x2 = x + N1; /* 次の座標 /*
y2 = y;
if(x2 == Z5) {
x2 = N0;
y2++;
}
if(ban[y][x] != NON) { /* 既に切手が置いてあった場合は次の座標へ /*
sub(ban , x2 , y2 , usedNo , cutPiece , mH3 , mH4 , n);
return;
}
for(i = N1 ; i <= N9 ; i++) { /* ３×３用の片を置く /*
if(usedNo[ID3][i] == N0) continue;
for(j = N0 ; j < nPiece[ID3][i] ; j++) {
if(okeruka(ban , x , y , i , j , ID3 , n , Z5) == OFF) continue;
usedNo[ID3][i]--;
cutPiece[ID3][mH3].n = i;
cutPiece[ID3][mH3].j = j;
sub(ban , x2 , y2 , usedNo , cutPiece , mH3 + N1 , mH4 , n + N1);
usedNo[ID3][i]++;
toru(ban , x , y , i , j , ID3);
}
}
for(i = N1 ; i <= N16 ; i++) { /* ４×４用の片を置く /*
if(usedNo[ID4][i] == N0) continue;
for(j = N0 ; j < nPiece[ID4][i] ; j++) {
if(okeruka(ban , x , y , i , j , ID4 , n , Z5) == OFF) continue;
usedNo[ID4][i]--;
cutPiece[ID4][mH4].n = i;
cutPiece[ID4][mH4].j = j;
sub(ban , x2 , y2 , usedNo , cutPiece , mH3 , mH4 + N1 , n + N1);
usedNo[ID4][i]++;
toru(ban , x , y , i , j , ID4);
}
}
}
/******************************************************************************
機能：引数で渡された切手枚数の片ごとに５×５を埋められるか探査する
引数：
(1) p0 : ３×３片の１個目の切手枚数
(2) p1 : ３×３片の２個目の切手枚数
(3) p2 : ４×４片の１個目の切手枚数
(4) p3 : ４×４片の２個目の切手枚数
戻り値：なし
*****************************************************************************/*
void set4(int p0 , int p1 , int p3 , int p4)
{
int usedNo[N2][N17]; /* 切手枚数ごとの片の使用数 /*
int i; /* ループの制御変数 /*
int x , y; /* 座標 /*
int p2 , p5; /* ３個目の数 /*
int ban[Z5][Z5]; /* 切手を置く盤 /*
CUTPIECE cutPiece[N2][NP3]; /* 使用する片 /*
for(i = N1 ; i <= N9 ; i++) usedNo[ID3][i] = N0; /* ０に初期化 /*
for(i = N1 ; i <= N16 ; i++) usedNo[ID4][i] = N0;
usedNo[ID3][p0]++; /* ３×３ １個目 /*
if(p1 > N0) usedNo[ID3][p1]++; /* ３×３ ２個目 /*
p2 = N9 - p0 - p1;
if(p2 > N0) usedNo[ID3][p2]++; /* ３×３ ３個目 /*
usedNo[ID4][p3]++; /* ４×４ １個目 /*
if(p4 > N0) usedNo[ID4][p4]++; /* ４×４ ２個目 /*
p5 = N16 - p3 - p4;
if(p5 > N0) usedNo[ID4][p5]++; /* ４×４ ３個目 /*
for(y = N0 ; y < Z5 ; y++) {
for(x = N0 ; x < Z5 ; x++) ban[y][x] = NON; /* 切手がない状態にする /*
}
sub(ban , N0 , N0 , usedNo , cutPiece , N0 , N0 , N0);
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：EXIT_SUCCESS
*****************************************************************************/*
int main(void)
{
int i , j , k; /* ループの制御変数 /*
for(i = N1 ; i <= N9 ; i++) { /* ３×３パターンを格納する領域の確保 /*
piece[ID3][i] = (PIECE *)malloc(sizeof(PIECE));
if(piece[ID3][i] == NULL) { /* メモリ確保エラー /*
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
}
for(i = N1 ; i <= N16 ; i++) { /* ４×４パターンを格納する領域の確保 /*
piece[ID4][i] = (PIECE *)malloc(sizeof(PIECE));
if(piece[ID4][i] == NULL) { /* メモリ確保エラー /*
for(i = N1 ; i <= N9 ; i++) free(piece[ID4][i]);
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
}
ban5 = (BAN5 *)malloc(sizeof(BAN5)); /* ５×５（解答）領域の確保 /*
if(ban5 == NULL) { /* メモリ確保エラー /*
for(i = N1 ; i <= N9 ; i++) free(piece[ID3][i]);
for(i = N1 ; i <= N16 ; i++) free(piece[ID4][i]);
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
init();
nH4[ID3] = NP1; /* ３×３を１個、４×４を３個の場合 /*
nH4[ID4] = NP3;
for(i = N1 ; i <= N16 ; i++) { /* ４×４片の１個目の切手枚数 /*
for(j = i ; j < N16 ; j++) { /* ４×４片の２個目の切手枚数 /*
k = N16 - i - j; /* ４×４片の３個目の切手枚数 /*
if(k < j) break;
set4(N9 , N0 , i , j);
}
}
nH4[ID3] = nH4[ID4] = NP2; /* ３×３を２個、４×４を２個の場合 /*
for(i = N1 ; i <= N9 ; i++) { /* ３×３片の１個目の切手枚数 /*
if(i > N9 - i) break; /* ３×３片の２個目の切手枚数 /*
for(j = i ; j <= N16 ; j++) { /* ４×４片の１個目の切手枚数 /*
if(j > N16 - j) break; /* ４×４片の２個目の切手枚数 /*
set4(i , N9 - i , j , N16 - j);
}
}
nH4[ID3] = NP3; /* ３×３を３個、４×４を１個の場合 /*
nH4[ID4] = NP1;
for(i = N1 ; i <= N9 ; i++) { /* ３×３片の１個目の切手枚数 /*
for(j = i ; j <= N9 ; j++) { /* ３×３片の２個目の切手枚数 /*
k = N9 - i - j; /* ３×３片の３個目の切手枚数 /*
if(k < j) break;
set4(i , j , N16 , N0);
}
}
free(ban5); /* メモリ開放 /*
for(i = N1 ; i <= N9 ; i++) free(piece[ID3][i]); /* メモリ開放 /*
for(i = N1 ; i <= N16 ; i++) free(piece[ID4][i]);
printf("%d通り\n" , nBan5);
return(EXIT_SUCCESS); /* 正常終了 /*
}
|
第160回（7月）カーペンターズ・パズル
|
|
/******************************************************************************
Ｃマガジン２００４年４月号電脳クラブ出題
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define N0 0 /* 基準の値 /*
#define N1 1 /* 単位の数 /*
#define N2 2 /* N1 + N1 /*
#define ERRMSG "malloc error at %d\n" /* メモリ確保エラーメッセージ /*
#define AKI "□" /* コインなし /*
#define COIN "●" /* コインあり /*
typedef struct {
unsigned int ban; /* 盤番号 /*
int min; /* その盤番号までの手数の最小値 /*
} BANMIN; /* 盤番号と最小手数の対応 /*
unsigned int *orBit; /* 盤番号ビット(OR) /*
unsigned int *andBit; /* 盤番号ビット(AND) /*
unsigned int startBan = N0 , goalBan = N0; /* 初期、終了時の盤番号 /*
BANMIN *banmin; /* 盤番号と最小手数の対応 /*
int fEnd = OFF; /* 探査終了フラグ /*
int nx; /* 盤の横方向の大きさ /*
int ny; /* 盤の縦方向の大きさ /*
int nxy; /* nx * ny /*
int nCoin = N0; /* コインの数 /*
int nBan , nBan1; /* 盤パターンの数、及びそのマイナス１ /*
unsigned int *hist; /* 最短手順 /*
int min = 1000000000; /* 最小手数 /*
static char *startJotai[] = { /* 盤の初期状態 /*
"*** " ,
"*** " ,
"*** " ,
" " };
static char *goalJotai[] = { /* 盤の終了状態 /*
" ***" ,
" ***" ,
" ***" ,
" " };
/******************************************************************************
機能：その盤の最小手数を求める。（２分岐探査）
引数：
(1) ban : 盤番号
戻り値：盤番号に対応する最小手数
*****************************************************************************/*
int getMin(unsigned int ban)
{
int is = N0 , ie , im; /* 下限、上限、中間 /*
ie = nBan;
while(N1) {
im = (is + ie) / N2;
if(banmin[im].ban == ban) return(banmin[im].min);
else if(banmin[im].ban < ban) is = im;
else ie = im;
}
}
/******************************************************************************
機能：その盤に最小値をセットする。（２分岐探査）
引数：
(1) ban : 盤番号
(2) min : 最小手数
戻り値：なし
*****************************************************************************/*
void setMin(unsigned int ban , int min)
{
int is = N0 , ie , im; /* 下限、上限、中間 /*
ie = nBan;
while(N1) {
im = (is + ie) / N2;
if(banmin[im].ban == ban) {
banmin[im].min = min;
return;
}
else if(banmin[im].ban < ban) is = im;
else ie = im;
}
}
/******************************************************************************
機能：盤の中のある場所の情報をセットする。
引数：
ban : 盤番号
pos : セットする座標番号
f1 : セットする値(OFF:コインなし、ON:コインあり)
戻り値：なし
*****************************************************************************/*
void setBan(unsigned int *ban , int pos , int f1)
{
if(f1 == OFF) *ban &= andBit[pos];
else *ban |= orBit[pos];
}
/******************************************************************************
機能：盤の中のある場所の情報を取得する。
引数：
ban : 盤番号
pos : 座標番号
戻り値：
OFF : コインがない
ON : コインがある
*****************************************************************************/*
int getBan(unsigned int ban , int pos)
{
int t1;
t1 = ban & orBit[pos];
if(t1 == N0) return(OFF);
else return(ON);
}
/******************************************************************************
機能：結果表示
引数：
n : 手数
戻り値：なし
*****************************************************************************/*
void disp(int n)
{
int i , j; /* ループの制御変数 /*
int t1; /* 一時変数 /*
for(i = N0 ; i < n ; i++) {
if(i == N0) printf("<初期状態>\n");
else printf("<%d手目>\n" , i);
for(j = N0 ; j < nxy ; j++) {
t1 = getBan(hist[i] , j); /* その座標にコインがあるか /*
if(t1 == OFF) printf(AKI); /* コインなし /*
else printf(COIN); /* コインあり /*
if(((j - nx + N1) % nx) == N0) printf("\n");
}
}
printf("<%d手目>\n" , n);
for(j = N0 ; j < nxy ; j++) {
t1 = getBan(goalBan , j); /* その座標にコインがあるか /*
if(t1 == OFF) printf(AKI); /* コインなし /*
else printf(COIN); /* コインあり /*
if(((j - nx + N1) % nx) == N0) printf("\n");
}
}
/******************************************************************************
機能：qsortの比較関数
引数：
(1) a : 左側ポインタ
(2) b : 右側ポインタ
戻り値：qsortの規定に従う。
*****************************************************************************/*
int cmp(const void **a , const void **b)
{
if (((BANMIN *)a)->ban < ((BANMIN *)b)->ban) return(-N1);
else if(((BANMIN *)a)->ban == ((BANMIN *)b)->ban) return(N0);
else return(N1);
}
int nn = N0;
/******************************************************************************
機能：全ての盤の番号を求める。
引数：
(1) r1 : コインの座標番号
(2) m : コインを置ける最初の座標
(3) n : 残りのコインの数
戻り値：なし
*****************************************************************************/*
void init2(int *coinZ , int m , int n)
{
int i;
if(n == N0) { /* コインを全部置いた /*
banmin[nn].ban = N0;
for(i = N0 ; i < nCoin ; i++) {
setBan(&(banmin[nn].ban) , coinZ[i] , ON);
}
nn++;
return;
}
for(i = m ; i < nxy ; i++) { /* コインを１個置いて次へ /*
coinZ[n - N1] = i;
init2(coinZ , i + N1 , n - N1);
}
}
/******************************************************************************
機能：理論上あり得る最小手数を求める。
引数：
(1) startCoin 移動前
(2) goalCoin 移動後
(3) n 残りのコイン
戻り値：なし
*****************************************************************************/*
void calcMin(int startCoin[] , int goalCoin[] , int n)
{
int i , j; /* ループの制御変数 /*
int tesu; /* 移動に必要な手数 /*
int sx , sy; /* コインの移動座標量 /*
int t1; /* 一時変数 /*
for(i = N0 ; i < n ; i++) {
t1 = goalCoin[i];
goalCoin[i] = goalCoin[n - N1];
goalCoin[n - N1] = t1;
if(n == N2) {
tesu = N0;
for(j = N0 ; j < nCoin ; j++) {
sx = abs(startCoin[j] % nx - goalCoin[j] % nx);
sy = abs(startCoin[j] / nx - goalCoin[j] / nx);
while(sx >= N2 && sy >= N2) {
sx -= N2; /* Ｘ、Ｙともにプラスマイナス２離れている /*
sy -= N2;
tesu++;
}
while(sx >= N2) {
sx -= N2; /* Ｘがプラスマイナス２離れている /*
tesu++;
}
while(sy >= N2) {
sy -= N2; /* Ｙがプラスマイナス２離れている /*
tesu++;
}
if(sx > N0) tesu++; /* Ｘがプラスマイナス１離れている /*
if(sy > N0) tesu++; /* Ｙがプラスマイナス１離れている /*
}
if(tesu < min) min = tesu;
}
else calcMin(startCoin , goalCoin , n - 1);
t1 = goalCoin[i];
goalCoin[i] = goalCoin[n - N1];
goalCoin[n - N1] = t1;
}
}
/******************************************************************************
機能：初期化
引数：なし
戻り値：なし
*****************************************************************************/*
void init(void)
{
int i , j; /* ループの制御変数 /*
int nw = N1; /* ２のコイン数乗−１ /*
int n = N0;
int x , y; /* 座標 /*
int t1 = N1 , t2 = N1; /* 一時変数 /*
int x1 = N0 , y1 = N0 , x2 = N0 , y2 = N0; /* 座標 /*
int *coinZ; /* コインの座標番号 /*
int *startCoin; /* 初期状態コインの座標番号 /*
int *goalCoin; /* 終了状態コインの座標番号 /*
static int sosu[] = {2 , 3 , 5 , 7}; /* 素数列 /*
ny = sizeof(startJotai) / sizeof(startJotai[N0]);
nx = strlen(startJotai[N0]);
nxy = nx * ny;
orBit = (int *)malloc(sizeof(int) * nxy);
if(orBit == NULL) {
fprintf(stderr , ERRMSG , __LINE__);
exit(EXIT_FAILURE);
}
andBit = (int *)malloc(sizeof(int) * nxy);
if(andBit == NULL) {
free(orBit);
fprintf(stderr , ERRMSG , __LINE__);
exit(EXIT_FAILURE);
}
for(i = N0 ; i < nxy ; i++) nw *= N2;
nw--;
orBit[N0] = N1;
for(i = N1 ; i < nxy ; i++) orBit[i] = orBit[i - N1] * N2;
for(i = N0 ; i < nxy ; i++) andBit[i] = nw - orBit[i];
for(y = N0 ; y < ny ; y++) {
for(x = N0 ; x < nx ; x++) {
if(*(startJotai[y] + x) == '*') {
setBan(&startBan , n , ON); /* 初期状態でコインあり /*
nCoin++; /* コインを数える /*
}
if(*(goalJotai[y] + x) == '*') {
setBan(&goalBan , n , ON); /* 終了状態でコインあり /*
}
n++;
}
}
startCoin = (int *)malloc(sizeof(int) * nCoin);
if(startCoin == NULL) {
free(orBit);
free(andBit);
fprintf(stderr , ERRMSG , __LINE__);
exit(EXIT_FAILURE);
}
n = N0;
for(y = N0 ; y < ny ; y++) { /* 初期状態のコインの座標番号 /*
for(x = N0 ; x < nx ; x++) {
if(*(startJotai[y] + x) == '*') startCoin[n++] = y * nx + x;
}
}
goalCoin = (int *)malloc(sizeof(int) * nCoin);
if(goalCoin == NULL) {
free(orBit);
free(andBit);
free(startCoin);
fprintf(stderr , ERRMSG , __LINE__);
exit(EXIT_FAILURE);
}
n = N0;
for(y = N0 ; y < ny ; y++) { /* 終了状態のコインの座標番号 /*
for(x = N0 ; x < nx ; x++) {
if(*(goalJotai[y] + x) == '*') goalCoin[n++] = y * nx + x;
}
}
n = N0;
for(i = N1 ; i <= nCoin ; i++) {
t1 *= (nxy - nCoin + i);
t2 *= i;
for(j = N0 ; j < sizeof(sosu) / sizeof(sosu[N0]) ; j++) {
while((t1 % sosu[j]) == N0 && (t2 % sosu[j]) == N0) {
t1 /= sosu[j]; /* オーバフローしないよう、あらかじめ約分 /*
t2 /= sosu[j];
}
}
}
nBan = t1 / t2;
nBan1 = nBan - N1;
banmin = (BANMIN *)malloc(sizeof(BANMIN) * (nBan + N1));
if(banmin == NULL) {
free(orBit);
free(andBit);
free(startCoin);
free(goalCoin);
fprintf(stderr , ERRMSG , __LINE__);
exit(EXIT_FAILURE);
}
coinZ = (int *)malloc(sizeof(int) * nCoin);
if(coinZ == NULL) {
free(orBit);
free(andBit);
free(startCoin);
free(goalCoin);
free(banmin);
fprintf(stderr , ERRMSG , __LINE__);
exit(EXIT_FAILURE);
}
init2(coinZ , N0 , nCoin);
free(coinZ);
qsort((void *)banmin , nBan , sizeof(BANMIN) , cmp);
banmin[nBan].min = banmin[nBan1].min;
banmin[nBan].ban = banmin[nBan1].ban;
calcMin(startCoin , goalCoin , nCoin);
free(startCoin);
free(goalCoin);
hist = (int *)malloc(sizeof(int) * nx * nCoin);
if(hist == NULL) {
free(orBit);
free(andBit);
free(banmin);
fprintf(stderr , ERRMSG , __LINE__);
exit(EXIT_FAILURE);
}
}
/******************************************************************************
機能：探査用再帰関数
引数：
(1) ban : 盤番号
(2) n : 手数
戻り値：なし
*****************************************************************************/*
void sub(unsigned int ban , int n)
{
int i; /* ループの制御変数（座標番号） /*
int x , y; /* 現在のコインの座標 /*
int n1; /* 次の手数 /*
int i1 , i2; /* コイン移動後の座標番号 /*
int dx , dy; /* 座標の増分 /*
int x1 , y1 , x2 , y2; /* コイン移動後の座標 /*
unsigned int t1; /* 一時変数 /*
if(fEnd == ON) return;
if(getMin(ban) <= n) return;
setMin(ban , n);
hist[n] = ban;
if(ban == goalBan) { /* ゴールにたどり着いたら /*
fEnd = ON; /* 終了フラグをONにする /*
disp(n); /* 途中の手順を表示する /*
return;
}
n1 = n + N1; /* 次の手数 /*
t1 = ban; /* 現在の盤番号を記録 /*
for(i = N0 ; i < nxy ; i++) {
if(getBan(ban , i) == OFF) continue;
x = i % nx; /* 現在のＸ座標 /*
y = i / nx; /* 現在のＹ座標 /*
for(dy = - N1 ; dy < N2 ; dy++) { /* Ｙ座標の増分 /*
y1 = y + dy; /* １マス移動後のＹ座標 /*
if(y1 == - N1 || y1 == ny) continue;
y2 = y1 + dy; /* ２マス移動後のＹ座標 /*
for(dx = - N1 ; dx < N2 ; dx++) { /* Ｘ座標の増分 /*
if(dx == N0 && dy == N0) continue;
x1 = x + dx; /* １マス移動後のＸ座標 /*
if(x1 == - N1 || x1 == nx) continue;
i1 = i + dx + nx * dy;
if(getBan(ban , i1) == OFF) { /* １マス動く /*
setBan(&ban , i , OFF);
setBan(&ban , i1 , ON);
sub(ban , n1);
ban = t1; /* 元に戻す /*
}
if(y2 == - N1 || y2 == ny) continue;
x2 = x1 + dx; /* ２マス移動後のＸ座標 /*
if(x2 == - N1 || x2 == nx) continue;
i2 = i1 + dx + nx * dy;
if(getBan(ban , i1) == ON && getBan(ban , i2) == OFF) {
setBan(&ban , i , OFF); /* ２マス動く /*
setBan(&ban , i2 , ON);
sub(ban , n1);
ban = t1; /* 元に戻す /*
}
}
}
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：EXIT_SUCCESS
*****************************************************************************/*
int main(void)
{
int i; /* ループの制御変数 /*
init(); /* 初期化処理 /*
while(fEnd == OFF) { /* 見つかるまでループする /*
for(i = N0 ; i <= nBan ; i++) banmin[i].min = min + N1;
sub(startBan , N0);
min++;
}
free(orBit);
free(andBit);
free(banmin);
free(hist);
return(EXIT_SUCCESS);
}
|
第158回（5月）肩のせ文字の誤植
|
|
/*****************************************************************************
肩のせ文字の誤植（Ｃマガジン２００４年２月号出題）
****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define N0 0 /* 原点 /*
#define N1 1 /* 1 /*
#define N2 2 /* 2 /*
#define N3 3 /* 3 /*
#define N4 4 /* 4 /*
#define N5 5 /* 5 /*
#define N6 6 /* 6 /*
#define N10 10 /* １０進数の１０ /*
#define N100 100 /* 10 * 10 /*
#define N1000 1000 /* 10 * 10 * 10 /*
#define N10000 10000 /* 10 * 10 * 10 * 10 /*
#define N100000 100000 /* 10 * 10 * 10 * 10 * 10 * 10 /*
#define N1000000 1000000 /* 10 * 10 * 10 * 10 * 10 * 10 * 10 /*
#define NPAT 10 /* ６桁をａ、ｂ、ｃに分ける桁数パターンの数 /*
typedef struct {
int a_k; /* ａの桁数−１ /*
int b_s; /* ｂの開始桁 /*
int b_k; /* ｂの桁数−１ /*
int c_s; /* ｃの開始桁 /*
int c_k; /* ｃの桁数−１ /*
} PAT; /* ６桁数字を３つに分割するパターン /*
PAT pat[NPAT];
int z0[N6][N4]; /* ６桁数字を１、２、３、４桁に分割した数 /*
/*****************************************************************************
機能：題意を満たすかどうかチェックし、満たすなら表示する。
引数：
(1) n5 : 右辺の６桁の数
戻り値：なし
****************************************************************************/*
void sub(int n5)
{
int i , j; /* ループの制御変数 /*
int s1; /* (a^b)*c /*
for(i = N0 ; i < NPAT ; i++) {
s1 = z0[pat[i].c_s][pat[i].c_k]; /* c /*
for(j = N0 ; j < z0[pat[i].b_s][pat[i].b_k] ; j++) {
s1 *= z0[N0][pat[i].a_k]; /* cにaをb個を掛け合わせる /*
if(s1 >= N1000000) break; /* 7桁以上になったらbreak /*
}
if(s1 == n5) printf("(%d,%d,%d)\n" , /* 正解なら表示する /*
z0[N0][pat[i].a_k] , z0[pat[i].b_s][pat[i].b_k] ,
z0[pat[i].c_s][pat[i].c_k]);
}
}
/*****************************************************************************
機能：メイン
引数：なし
戻り値：EXIT_SUCCESS
****************************************************************************/*
int main(void)
{
int i , j; /* ループの制御変数 /*
int n = N0;
int d0_0 , d0_1 , d0_2 , d0_3; /* 10万の位 *10、*100、*1000 /*
int d1_0 , d1_1 , d1_2 , d1_3; /* 1万の位 *10、*100、*1000 /*
int d2_0 , d2_1 , d2_2 , d2_3; /* 1000の位 *10、*100、*1000 /*
int d3_0 , d3_1 , d3_2; /* 100の位 *10、*100 /*
int d4_0 , d4_1; /* 100の位 *10 /*
int d5_0; /* 1の位 /*
int n0 , n1 , n2 , n3 , n4 , n5; /* ６桁の数の値(各桁まで) /*
for(i = N0 ; i < N4 ; i++) { /* 初期化 /*
for(j = N0 ; j < N4 - i ; j++) {
pat[n].a_k = i;
pat[n].b_s = pat[n].a_k + N1;
pat[n].b_k = j;
pat[n].c_s = pat[n].a_k + pat[n].b_k + N2;
pat[n].c_k = N5 - pat[n].c_s;
n++;
}
}
for(d0_0 = N1 ; d0_0 < N10 ; d0_0++) { /* 10万の位 /*
d0_1 = d0_0 * N10;
d0_2 = d0_0 * N100;
d0_3 = d0_0 * N1000;
n0 = d0_0 * N100000;
z0[N0][N0] = d0_0;
for(d1_0 = N0 ; d1_0 < N10 ; d1_0++) { /* 1万の位 /*
d1_1 = d1_0 * N10;
d1_2 = d1_0 * N100;
n1 = n0 + d1_0 * N10000;
z0[N1][N0] = d1_0;
z0[N0][N1] = d0_0 * N10 + z0[N1][N0];
d1_3 = d1_0 * N1000;
for(d2_0 = N0 ; d2_0 < N10 ; d2_0++) { /* 1000の位 /*
d2_1 = d2_0 * N10;
d2_2 = d2_0 * N100;
d2_3 = d2_0 * N1000;
n2 = n1 + d2_3;
z0[N2][N0] = d2_0;
z0[N1][N1] = d1_1 + z0[N2][N0];
z0[N0][N2] = d0_2 + z0[N1][N1];
for(d3_0 = N0 ; d3_0 < N10 ; d3_0++) { /* 100の位 /*
d3_1 = d3_0 * N10;
d3_2 = d3_0 * N100;
n3 = n2 + d3_2;
z0[N3][N0] = d3_0;
z0[N2][N1] = d2_1 + z0[N3][N0];
z0[N1][N2] = d1_2 + z0[N2][N1];
z0[N0][N3] = d0_3 + z0[N1][N2];
for(d4_0 = N0 ; d4_0 < 10 ; d4_0++) { /* 10の位 /*
d4_1 = d4_0 * N10;
n4 = n3 + d4_1;
z0[N4][N0] = d4_0;
z0[N3][N1] = d3_1 + z0[N4][N0];
z0[N2][N2] = d2_2 + z0[N3][N1];
z0[N1][N3] = d1_3 + z0[N2][N2];
for(d5_0 = N0 ; d5_0 < N10 ; d5_0++) { /* 1の位 /*
n5 = n4 + d5_0;
z0[N5][N0] = d5_0;
z0[N4][N1] = d4_1 + z0[N5][N0];
z0[N3][N2] = d3_2 + z0[N4][N1];
z0[N2][N3] = d2_3 + z0[N3][N2];
sub(n5);
}
}
}
}
}
}
return(EXIT_SUCCESS);
}
|
第156回（3月）ダブりペントミノ
|
|
/******************************************************************************
ダブりペントミノ（Ｃマガジン２００３年１２月電脳クラブ出題）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define NON -1 /* まだ置いてない /*
#define N0 0 /* 基準値 /*
#define N1 1 /* 単位の数 /*
#define N2 2 /* N1 + N1 /*
#define N5 5 /* ペントミノを構成する座標の数 /*
#define N7 7 /* ペントミノの数 /*
#define N8 8 /* ペントミノの回転、反転などの数 /*
#define B6 6 /* B7 - N1 /*
#define B7 7 /* 盤（ペースを詰める正方形）の１辺の長さ /*
typedef struct {
int x; /* Ｘ /*
int y; /* Ｙ /*
} XY;
XY pen2[N7][N8][N5]; /* 回転、反転したペントミノの座標 /*
int nPen2[N7]; /* 鏡像の個数 /*
int ban[B7][B7]; /* 盤（正方形） /*
int used[N7]; /* ペントミノを使用できる個数 /*
/******************************************************************************
機能：ｑｓｏｒｔ用比較関数
引数：
a : 比較対象a
b : 比較対象b
戻り値：
-1 : a < b
0 : a == b
1 : a > b
*****************************************************************************/*
int cmp(const void *a , const void *b)
{
if (((XY *)a)->y < ((XY *)b)->y) return(-N1);
else if(((XY *)a)->y == ((XY *)b)->y) {
if (((XY *)a)->x < ((XY *)b)->x) return(-N1);
else if(((XY *)a)->x == ((XY *)b)->x) return(N0);
else return(N1);
}
else return(N1);
}
/******************************************************************************
機能：初期化
引数：なし
戻り値：なし
*****************************************************************************/*
void init(void)
{
int x , y; /* 座標 /*
int i , j , k , l; /* ループの制御変数 /*
int n; /* 鏡像の個数 /*
int xmin , ymin; /* 原点位置 /*
static XY pen1[N7][N5] = { /* ペントミノの座標の定義 /*
0,0 , 0,1 , 0,2 , 0,3 , 0,4 , /* ｜ /*
0,0 , 1,0 , 0,1 , 0,2 , 0,3 , /* 」 /*
0,0 , 0,1 , 0,2 , 1,2 , 0,3 , /* ト /*
0,0 , -1,1 , 0,1 , 1,1 , 0,2 , /* ＋ /*
0,0 , 1,0 , 0,1 , 0,2 , -1,2 , /* Ｚ /*
0,0 , 1,0 , 2,0 , 0,1 , 0,2 , /* Ｌ /*
0,0 , 1,0 , 2,0 , 0,1 , 2,1 /* 凹 /* };
static XY dxy[N8][N2] = { /* 鏡像パターン /*
1,0,0,1 , -1, 0,0,1 , 1,0, 0,-1 , -1, 0, 0,-1 ,
0,1,1,0 , 0,-1,1,0 , 0,1,-1, 0 , 0,-1,-1, 0 };
for(y = N0 ; y < B7 ; y++) { /* 盤を初期化 /*
for(x = N0 ; x < B7 ; x++) ban[y][x] = NON;
}
for(y = N1 ; y < N7 ; y += N2) { /* 盤を初期化（置けない場所） /*
for(x = N1 ; x < N7 ; x += N2) ban[y][x] = N7;
}
for(i = 0 ; i < N7 ; i++) { /* 鏡像生成 /*
n = 0;
for(j = N0 ; j < N8 ; j++) { /* 鏡像８パターン /*
ymin = N7;
for(k = N0 ; k < N5 ; k++) { /* 回転・反転後の座標 /*
pen2[i][n][k].x = pen1[i][k].x * dxy[j][N0].x +
pen1[i][k].y * dxy[j][N0].y;
pen2[i][n][k].y = pen1[i][k].x * dxy[j][N1].x +
pen1[i][k].y * dxy[j][N1].y;
if(pen2[i][n][k].y < ymin) {
ymin = pen2[i][n][k].y;
xmin = pen2[i][n][k].x;
}
else if(pen2[i][n][k].y == ymin) {
if(pen2[i][n][k].x < xmin) xmin = pen2[i][n][k].x;
}
} /* 原点移動 /*
for(k = N0 ; k < N5 ; k++) {
pen2[i][n][k].x -= xmin;
pen2[i][n][k].y -= ymin;
}
qsort(pen2[i][n] , N5 , sizeof(XY) , cmp); /* 座標順に並べる /*
for(k = N0 ; k < n ; k++) { /* 既出パターンかどうかのチェック /*
for(l = N0 ; l < N5 ; l++) {
if(pen2[i][n][l].x != pen2[i][k][l].x) break;
if(pen2[i][n][l].y != pen2[i][k][l].y) break;
}
if(l == N5) break;
}
if(k == n) n++; /* 初出パターンならカウントアップ /*
}
nPen2[i] = n; /* 鏡像の個数を登録 /*
}
}
/******************************************************************************
機能：解答表示
引数：なし
戻り値：なし
*****************************************************************************/*
void disp(void)
{
int x , y;
printf("-------\n");
for(y = N0 ; y < B7 ; y++) {
for(x = N0 ; x < B7 ; x++) {
if(ban[y][x] == N7) printf("*");
else printf("%d" , ban[y][x]);
}
printf("\n");
}
}
/******************************************************************************
機能：再帰呼び出し関数
引数：
x : Ｘ座標
y : Ｙ座標
戻り値：なし
*****************************************************************************/*
void sub(int x , int y)
{
int i , j , k; /* ループの制御変数 /*
int x2 , y2; /* 座標 /*
if(y == B7) { /* 全部置いた場合 /*
if(ban[N0][N0] > ban[N0][B6]) return; /* 鏡像チェック /*
if(ban[N0][N0] > ban[B6][N0]) return;
if(ban[N0][N0] > ban[B6][B6]) return;
if(ban[B6][N0] > ban[N0][B6]) return;
if(ban[N0][N0] == ban[B6][N0] && ban[N0][B6] > ban[B6][B6]) return;
disp(); /* 鏡像でなければ解答表示 /*
return;
}
if(x == B7) { /* 右端に達した場合 /*
x = N0;
y++;
}
if(ban[y][x] != NON) sub(x + N1 , y);
for(i = N0 ; i < N7 ; i++) {
if(used[i] == N0) continue; /* 使用済みならスキップ /*
used[i]--; /* １個使用済みにする /*
for(j = N0 ; j < nPen2[i] ; j++) {
for(k = N0 ; k < N5 ; k++) { /* 置けるかどうかのチェック /*
x2 = x + pen2[i][j][k].x;
if(x2 < N0 || x2 > B6) break; /* ペントミノが正方形の外 /*
y2 = y + pen2[i][j][k].y;
if(y2 < N0 || y2 > B6) break;
if(ban[y2][x2] != NON) break;
}
if(k != N5) continue; /* 置けないならスキップ /*
for(k = N0 ; k < N5 ; k++) {
ban[y + pen2[i][j][k].y][x + pen2[i][j][k].x] = i; /* 置く /*
}
sub(x + N1 , y); /* 次の座標（右へ１つ）へ /*
for(k = N0 ; k < N5 ; k++) {
ban[y + pen2[i][j][k].y][x + pen2[i][j][k].x] = NON; /* 取る /*
}
}
used[i]++; /* １個未使用に戻す /*
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：０
*****************************************************************************/*
int main(void)
{
int i;
init(); /* 初期化 /*
for(i = N0 ; i < N7 ; i++) used[i] = N1;
for(i = N0 ; i < N7 ; i++) { /* １個追加するペントミノの番号 /*
used[i]++; /* １個追加 /*
sub(N0 , N0);
used[i]--; /* 元に戻す /*
}
return(EXIT_SUCCESS);
}
|
第155回（2月）十五長方形合流記
|
|
/******************************************************************************
Ｃマガジン２００３年１１月号 電脳クラブ（十五長方形合流記）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N0 0 /* 基準値 /*
#define N1 1 /* 単位の数 /*
#define N2 2 /* N1 + N1 /*
#define NON -1 /* 未使用 /*
#define MOJI 'A' /* 解答例表示の文字 /*
static int rect[][N2] = { /* 長方形の定義 /*
13,60 , 15,37 , 16,41 , 17,51 , 18,48 ,
19,56 , 20,44 , 21,29 , 23,32 , 24,31 ,
25,27 , 26,61 , 28,40 , 30,43 , 42,47 };
int *square; /* 正方形 NON:置かれてない、>NON:長方形が置かれている /*
int *sRect; /* 長方形の状態 NON:未使用、N0:ＸＹ反転、N1:そのまま /*
int count = N0; /* 解答 /*
int nRect; /* 長方形の数 /*
int len; /* 正方形の辺の長さ /*
int len1; /* len - N1 /*
int zCorner1 , zCorner2; /* 正方形の角 /*
int last_no; /* 最後に置いた長方形の番号 /*
int *unused; /* 未使用の長方形の番号一覧 /*
/******************************************************************************
機能：解答例表示
引数：なし
戻り値：なし
*****************************************************************************/*
void disp(void)
{
int i; /* ループの制御変数 /*
int x , y; /* 座標 /*
int t1; /* 一時変数 /*
int no; /* 長方形の番号 /*
printf("解答例\n");
for(y = N0 ; y < len ; y++) {
t1 = y * len;
x = N0;
while(x < len) {
no = square[t1 + x]; /* その場所の長方形の番号（左端） /*
for(i = N0 ; i < rect[no][sRect[no]] ; i++) {
printf("%c" , MOJI + no); /* Ｘ方向の長さ分、描画する /*
x++;
}
}
printf("\n");
}
printf("\n");
for(i = N0 ; i < nRect ; i++) { /* 凡例 /*
printf("%c : %3d * %3d\n" , MOJI + i , rect[i][N0] , rect[i][N1]);
}
}
/******************************************************************************
機能：再帰呼び出し関数（長方形を１個置く）
引数：
xp : Ｘ座標
yp : Ｙ座標
n : これまでに置いた長方形の個数
戻り値：なし
*****************************************************************************/*
void sub(int xp , int yp , int n)
{
int i; /* ループの制御変数 /*
int x , y; /* 座標 /*
int idx , idy; /* /*
int n2; /* /*
int t1; /* 一時変数 /*
int no; /* 長方形の番号 /*
if(n == nRect) { /* 全ての長方形を置いた場合 /*
if(square[zCorner2] < square[zCorner1]) return; /* 鏡像チェック /*
if(last_no < square[zCorner1]) return; /* 鏡像チェック /*
if(count == N0) disp(); /* １個目なら解答例を表示 /*
count++; /* カウントアップ /*
return;
}
if(xp == len) { /* 右端に達した /*
if(yp == N0 && last_no < square[zCorner1]) return;
xp = N0;
yp++;
}
no = square[yp * len + xp]; /* その場所の状態 /*
if(no != NON) { /* 既に長方形が置かれている /*
sub(xp + rect[no][sRect[no]] , yp , n); /* 次へ /*
return;
}
n2 = n + N1; /* 今回置いた後の長方形の数 /*
for(idy = N0 ; idy < N2 ; idy++) { /* NO:そのまま、N1:ＸＹ反転 /*
idx = N1 - idy;
for(i = N0 ; i < nRect - n ; i++) {
no = unused[i];
unused[i] = unused[nRect - n2];
for(y = N0 ; y < rect[no][idy] ; y++) { /* 長方形を置けるか？ /*
t1 = (yp + y) * len + xp;
for(x = N0 ; x < rect[no][idx] ; x++) {
if(square[t1++] != NON) break; /* 既に長方形あり /*
}
if(x != rect[no][idx]) break;
}
if(y == rect[no][idy]) { /* 長方形を置ける場合 /*
for(y = N0 ; y < rect[no][idy] ; y++) {
square[(yp + y) * len + xp] = no; /* 長方形を置く /*
}
sRect[no] = idx; /* 使用済みにする /*
last_no = no;
sub(xp + rect[no][idx] , yp , n2);
sRect[no] = NON; /* 未使用に戻す /*
for(y = N0 ; y < rect[no][idy] ; y++) {
square[(yp + y) * len + xp] = NON; /* 長方形を取る /*
}
}
unused[i] = no;
}
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：０
*****************************************************************************/*
int main(void)
{
int x , y; /* 座標 /*
int i; /* ループの制御変数 /*
int s = N0; /* 正方形の面積 /*
int t1; /* 一時変数 /*
int no;
nRect = sizeof(rect) / sizeof(rect[N0]); /* 長方形の数を求める /*
for(i = N0 ; i < nRect ; i++) { /* 正方形の面積を求める /*
s += rect[i][N0] * rect[i][N1];
}
len = (int)sqrt((double)s); /* 辺の長さを求める /*
if(len * len != s) {
fprintf(stderr , "長方形を合流しても正方形になりません\n");
exit(EXIT_FAILURE);
}
len1 = len - N1;
zCorner1 = N0 * len + N0; /* 正方形の角 /*
zCorner2 = len1 * len + N0; /* 正方形の角 /*
square = (int *)malloc(sizeof(int) * len * len); /* 正方形メモリ確保 /*
if(square == NULL) {
fprintf(stderr , "mallocエラー at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
sRect = (int *)malloc(sizeof(int) * nRect); /* 状態メモリ確保 /*
if(sRect == NULL) {
free(square);
fprintf(stderr , "mallocエラー at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
unused = (int *)malloc(sizeof(int) * nRect); /* 未使用長方形メモリ確保 /*
if(unused == NULL) {
free(square);
free(sRect);
fprintf(stderr , "mallocエラー at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
for(i = N0 ; i < nRect ; i++) {
sRect[i] = NON; /* 全て未使用にする /*
unused[i] = i;
}
for(y = N0 ; y < len ; y++) {
t1 = y * len;
for(x = N0 ; x < len ; x++) square[t1++] = NON; /* 置いてない状態 /*
}
for(i = N0 ; i < nRect ; i++) { /* １個目の長方形（向き固定） /*
no = unused[i];
unused[i] = unused[nRect - N1];
for(y = N0 ; y < rect[no][N0] ; y++) square[y * len] = no; /* 置く /*
sRect[no] = N1; /* 使用済みにする /*
sub(rect[no][N1] , N0 , N1); /* １個置いて次へ /*
sRect[no] = NON; /* 未使用に戻す /*
for(y = N0 ; y < rect[no][N0] ; y++) square[y * len] = NON; /* 取る /*
unused[i] = no;
}
printf("解答：%d通り\n" , count);
free(unused);
free(sRect);
free(square);
return(EXIT_SUCCESS);
}
|
第154回（1月）どろけい
|
|
/******************************************************************************
Ｃマガジン２００３年１０月電脳クラブ出題（どろけい）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define N0 0 /* 基準値 /*
#define N1 1 /* 単位の数 /*
#define N2 2 /* N1 + N1 /*
#define N3 3 /* 一つの座標から遷移でいる座標数の最大 /*
#define N6 6 /* 座標の数 /*
#define DAN 3 /* 解答例で、段の数 /*
#define DAN0 0 /* 上段 /*
#define DAN1 1 /* 中段 /*
#define DAN2 2 /* 下段 /*
#define POS0 0 /* 上＆中央 /*
#define POS1 1 /* 中＆左 /*
#define POS2 2 /* 下＆左 /*
#define POS3 3 /* 下＆右 /*
#define POS4 4 /* 中＆右 /*
#define POS5 5 /* 中＆中 /*
#define N72 72 /* N6 * N6 * N2（刑事、泥棒を合わせた局面の数） /*
#define NOLINK -1 /* リンクなし /*
#define KPOS POS5 /* 刑事の初期座標 /*
#define DPOS POS4 /* 泥棒の初期座標 /*
#define KEIJI "刑" /* 手順表示（刑事のシンボル） /*
#define DOROBO "泥" /* 手順表示（泥棒のシンボル） /*
#define HOKAKU "捕" /* 手順表示（捕獲場所のシンボル） /*
#define NON "○" /* 手順表示（刑事も泥棒もいない場所） /*
#define SPACE " " /* 手順表示（空白） /*
#define YA "→" /* 手順表示（矢印） /*
#define TE "手" /* 正解表示で使用する単位 /*
static int link[][N3] = { /* 座標間のリンク情報 /*
POS1 , POS5 , POS4 ,
POS0 , POS2 , NOLINK ,
POS1 , POS5 , POS3 ,
POS2 , POS5 , POS4 ,
POS0 , POS3 , NOLINK ,
POS0 , POS2 , POS3 };
int min = N1; /* 最小手数（この範囲で探索する） /*
int fPass[N6][N6]; /* そのパターンを通過済みどうかのフラグ /*
int tejun[N72]; /* 最善手順 /*
int moveKei(int , int , int); /* プロトタイプ宣言 /*
void moveKei2(int , int , int); /* プロトタイプ宣言 /*
/******************************************************************************
機能：手順を表示する（１座標ずつ）
引数：
(1) keiPos : 刑事の座標
(2) doroPos : 泥棒の座標
(3) pos : 結果を表示する座標
戻り値：なし
*****************************************************************************/*
void disp1(int keiPos , int doroPos , int pos)
{
if (keiPos == pos && doroPos == pos) printf(HOKAKU); /* 捕獲 /*
else if(keiPos == pos) printf(KEIJI); /* 刑事 /*
else if(doroPos == pos) printf(DOROBO); /* 泥棒 /*
else printf(NON); /* いない /*
}
/******************************************************************************
機能：手順を表示する（１段ずつ）
引数：
(1) keiPos : 刑事の座標
(2) doroPos : 泥棒の座標
(3) dan : 段
(4) x : 横方向
戻り値：なし
*****************************************************************************/*
void dispDan(int keiPos , int doroPos , int dan , int x)
{
if (dan == DAN0) printf(SPACE); /* 上段 /*
else if(dan == DAN2) printf(" "); /* 下段 /*
if(dan == DAN0) { /* 上段 /*
disp1(keiPos , doroPos , POS0);
}
else if(dan == DAN1) { /* 中段 /*
disp1(keiPos , doroPos , POS1);
disp1(keiPos , doroPos , POS5);
disp1(keiPos , doroPos , POS4);
}
else if(dan == DAN2) { /* 下段 /*
disp1(keiPos , doroPos , POS2);
disp1(keiPos , doroPos , POS3);
}
if(x < min) {
if (dan == DAN0) { /* 上段 /*
printf(SPACE);
printf(SPACE);
}
else if(dan == DAN2) { /* 下段 /*
printf(" ");
printf(SPACE);
}
else if(dan == DAN1) printf(YA); /* 中段 /*
}
else printf("\n"); /* 右端では改行 /*
}
/******************************************************************************
機能：手順を表示する（全体）
引数：なし
戻り値：なし
*****************************************************************************/*
void dispTejun(void)
{
int i , j;
int keiPos , doroPos;
printf("\n");
for(i = N0 ; i < DAN ; i++) { /* 手順表示 /*
keiPos = KPOS; /* 刑事、泥棒の座標を初期化 /*
doroPos = DPOS;
for(j = N0 ; j < min ; j += N2) {
dispDan(keiPos , doroPos , i , j);
keiPos = tejun[j]; /* 最善手順で刑事を動かす /*
dispDan(keiPos , doroPos , i , j + N1);
doroPos = tejun[j + N1]; /* 最善手順で泥棒を動かす /*
}
}
}
/******************************************************************************
機能：泥棒を動かす（最短手順探索用）
引数：
(1) keiPos : 刑事の座標
(2) doroPos : 泥棒の座標
(3) n : ここまでの手数（０オリジン）
戻り値：この局面で泥棒が最善手を尽くした場合の手数
*****************************************************************************/*
int moveDoro(int keiPos , int doroPos , int n)
{
int i; /* ループの制御変数 /*
int nextPos; /* 次の座標 /*
int bestTe = N0 , te;
if(keiPos == doroPos) return(n); /* 捕獲されたら探索中止 /*
for(i = N0 ; i < N3 ; i++) {
nextPos = link[doroPos][i]; /* 次の手（候補） /*
if(nextPos == NOLINK) continue; /* リンク先がない /*
if(keiPos == nextPos) continue; /* そこには刑事がいた /*
te = moveKei(keiPos , nextPos , n + N1); /* 手数 /*
if(te > bestTe) bestTe = te; /* より多い手数を最善手数とする /*
}
return(bestTe); /* 手数を返す /*
}
/******************************************************************************
機能：刑事を動かす（最短手順探索用）
引数：
(1) keiPos : 刑事の座標
(2) doroPos : 泥棒の座標
(3) n : ここまでの手数（０オリジン）
戻り値：この局面で刑事が最善手を尽くした場合の手数
*****************************************************************************/*
int moveKei(int keiPos , int doroPos , int n)
{
int i; /* ループの制御変数 /*
int nextPos; /* 次の座標 /*
int bestTe = N72 , te;
if(min < n) return(n);
for(i = N0 ; i < N3 ; i++) {
nextPos = link[keiPos][i]; /* 次の手（候補） /*
if(nextPos == NOLINK) continue; /* リンク先がない /*
if(fPass[nextPos][doroPos] == ON) continue; /* 通過済みの局面 /*
fPass[nextPos][doroPos] = ON; /* 通過済みとする /*
te = moveDoro(nextPos , doroPos , n + N1); /* 手数 /*
fPass[nextPos][doroPos] = OFF; /* 通過済みを解除する /*
if(te < bestTe) bestTe = te; /* より少ない手数を最善手数とする /*
}
return(bestTe); /* 手数を返す /*
}
/******************************************************************************
機能：泥棒を動かす（手順表示用）
引数：
(1) keiPos : 刑事の座標
(2) doroPos : 泥棒の座標
(3) n : ここまでの手数（０オリジン）
戻り値：この局面で泥棒が最善手を尽くした場合の手数
*****************************************************************************/*
void moveDoro2(int keiPos , int doroPos , int n)
{
int i; /* ループの制御変数 /*
int nextPos; /* 次の座標 /*
int bestTe = N0 , te;
int rTe[N3];
if(keiPos == doroPos) {
dispTejun();
return; /* 捕獲されたら手順を表示して探索中止 /*
}
for(i = N0 ; i < N3 ; i++) {
rTe[i] = N0;
nextPos = link[doroPos][i]; /* 次の手（候補） /*
if(nextPos == NOLINK) continue; /* リンク先がない /*
if(keiPos == nextPos) continue; /* そこには刑事がいた /*
rTe[i] = te = moveKei(keiPos , nextPos , n + N1); /* 手数 /*
if(te > bestTe) bestTe = te; /* より多い手数を最善手数とする /*
}
for(i = N0 ; i < N3 ; i++) {
if(rTe[i] != bestTe) continue;
tejun[n] = link[doroPos][i]; /* 最善手順を登録する /*
moveKei2(keiPos , tejun[n] , n + N1); /* 次の刑事移動へ /*
}
}
/******************************************************************************
機能：刑事を動かす（手順表示用）
引数：
(1) keiPos : 刑事の座標
(2) doroPos : 泥棒の座標
(3) n : ここまでの手数（０オリジン）
戻り値：この局面で刑事が最善手を尽くした場合の手数
*****************************************************************************/*
void moveKei2(int keiPos , int doroPos , int n)
{
int i; /* ループの制御変数 /*
int nextPos; /* 次の座標 /*
int bestTe = N72 , te;
int rTe[N3];
if(min < n) return;
for(i = N0 ; i < N3 ; i++) {
rTe[i] = N72;
nextPos = link[keiPos][i]; /* 次の手（候補） /*
if(nextPos == NOLINK) continue; /* リンク先がない /*
if(fPass[nextPos][doroPos] == ON) continue; /* 通過済みの局面 /*
fPass[nextPos][doroPos] = ON; /* 通過済みとする /*
rTe[i] = te = moveDoro(nextPos , doroPos , n + N1); /* 手数 /*
fPass[nextPos][doroPos] = OFF; /* 通過済みを解除する /*
if(te < bestTe) bestTe = te; /* より少ない手数を最善手数とする /*
}
for(i = N0 ; i < N3; i++) {
if(rTe[i] != bestTe) continue;
tejun[n] = link[keiPos][i]; /* 最善手順を登録する /*
moveDoro2(tejun[n] , doroPos , n + N1); /* 次の泥棒移動へ /*
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：０
*****************************************************************************/*
int main(void)
{
int i , j; /* ループの制御変数 /*
for(i = N0 ; i < N6 ; i++) { /* 通過フラグを初期化 /*
for(j = N0 ; j < N6 ; j++) fPass[i][j] = OFF;
}
while(moveKei(KPOS , DPOS , N0) != min) min += N2; /* 解答を探索する /*
printf("最短手順：%d手\n" , min); /* 解答表示 /*
moveKei2(KPOS , DPOS , N0); /* 手順表示 /*
return(EXIT_SUCCESS);
}
| | | | | | |