/******************************************************************************
Ｃマガジン２００２年９月出題 電脳クラブ（クロ交換シロ）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define NON 0 /* 何も置いてない /*
#define BLACK 1 /* 黒 /*
#define WHITE 2 /* 白 /*
#define ORG 0 /* 原点 /*
#define NOTUSED -1 /* 未使用 /*
#define SHOKI -1 /* １手目における前回手 /*
#define N1 1 /* 最小単位 /*
#define N3 3 /* 状態(なし、黒、白)の数 /*
#define N6 6 /* コマの数 /*
#define NM 4 /* 移動可能な個所の最大数 /*
#define W1(y , x) (y) * sizeX + (x) /* work用データ取得 /*
#define M1(a , b) a * NM + b /* move用データ取得 /*
int nb = ORG; /* 盤上でコマを置ける個所の数 /*
int np = N1; /* 盤のパターンの数 /*
int *min = NULL; /* その盤のパターンにたどり着いた最小手数 /*
int *ban = NULL; /* 盤 /*
int endId; /* 終了ＩＤ /*
int *move = NULL; /* 移動先 /*
int *nMove = NULL; /* 移動先の数 /*
int fFind = OFF;
/******************************************************************************
機能：終了処理（確保したメモリの開放）
引数：なし
戻り値：なし
*****************************************************************************/*
void end(void)
{
free(min);
free(ban);
free(nMove);
free(move);
}
#define B 'B' /* 黒コマ /*
#define W 'W' /* 白コマ /*
#define STAR '*' /* 盤の外 /*
/******************************************************************************
機能：ＩＤを求める。
引数：パターン
戻り値：ＩＤ
*****************************************************************************/*
int getId(int pat[])
{
int id = ORG; /* ＩＤ /*
int i; /* ループの制御変数 /*
for(i = ORG ; i < nb ; i++) id = id * N3 + pat[i];
return(id);
}
/******************************************************************************
機能：初期化
引数：なし
戻り値：なし
*****************************************************************************/*
void init(void)
{
static char *banDef[] = { /* 盤初期状態の定義 /*
"** *" ,
"**B*" ,
"**B*" ,
" WB " ,
"*W**" ,
"*W**" ,
"* **" };
int *work; /* 移動先データ取得用ワーク /*
int x , y;
int sizeX , sizeY; /* 盤の大きさ /*
int n;
int *endP; /* 終了パターン /*
int i; /* ループの制御変数 /*
sizeX = strlen(banDef[ORG]);
sizeY = sizeof(banDef) / sizeof(banDef[ORG]);
work = (int *)malloc(sizeof(int) * sizeX * sizeY);
if(work == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
end();
exit(EXIT_FAILURE);
}
for(y = ORG ; y < sizeY ; y++) {
for(x = ORG ; x < sizeX ; x++) {
work[W1(y , x)] = NOTUSED;
if(*(banDef[y] + x) == STAR) continue;
ban = (int *)realloc(ban , sizeof(int) * (nb + N1));
if(ban == NULL) {
fprintf(stderr , "realloc error at %d\n" , __LINE__);
end();
exit(EXIT_FAILURE);
}
if (*(banDef[y] + x) == B) ban[nb] = BLACK;
else if(*(banDef[y] + x) == W) ban[nb] = WHITE;
else ban[nb] = NON;
work[W1(y , x)] = nb;
nb++;
np *= N3;
}
}
nMove = (int *)malloc(sizeof(int) * nb);
if(nMove == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
end();
exit(EXIT_FAILURE);
}
move =(int *)malloc(sizeof(int *) * nb * NM);
if(move == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
end();
exit(EXIT_FAILURE);
}
for(y = ORG ; y < sizeY ; y++) {
for(x = ORG ; x < sizeX ; x++) {
if(work[W1(y , x)] == NOTUSED) continue;
n = ORG;
if(x > ORG) { /* ← /*
if(work[W1(y , x - N1)] != NOTUSED) {
move[M1(work[W1(y , x)] , n++)] = work[W1(y , x - N1)];
}
}
if(x < sizeX - N1) { /* → /*
if(work[W1(y , x + N1)] != NOTUSED) {
move[M1(work[W1(y , x)] , n++)] = work[W1(y , x + N1)];
}
}
if(y > ORG) { /* ↑ /*
if(work[W1(y - N1 , x)] != NOTUSED) {
move[M1(work[W1(y , x)] , n++)] = work[W1(y - N1 ,x)];
}
}
if(y < sizeY - N1) { /* ↓ /*
if(work[W1(y + N1 , x)] != NOTUSED) {
move[M1(work[W1(y , x)] , n++)] = work[W1(y + N1 , x)];
}
}
nMove[work[W1(y , x)]] = n;
}
}
free(work);
min = (int *)malloc(sizeof(int) * np);
if(min == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
end();
exit(EXIT_FAILURE);
}
endP = (int *)malloc(sizeof(int) * nb);
if(endP == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
end();
exit(EXIT_FAILURE);
}
for(i = ORG ; i < nb ; i++) { /* 終了パターンを求める /*
if (ban[i] == NON) endP[i] = NON;
else if(ban[i] == BLACK) endP[i] = WHITE;
else endP[i] = BLACK;
}
endId = getId(endP); /* 終了ＩＤを求める /*
free(endP);
}
/******************************************************************************
機能：再帰呼び出し関数
引数：
n (I) ここまでの手数
pos (I) 前回動いたコマの移動先
戻り値：なし
*****************************************************************************/*
void sub(int n , int pos)
{
int i , j; /* ループの制御変数 /*
int n1; /* n + 1 /*
int id; /* ＩＤ /*
id = getId(ban); /* 現ＩＤを求める /*
if(min[id] <= n) return; /* 過去に、より少ない手数で来ている /*
min[id] = n; /* 手数を登録 /*
if(id == endId) { /* 終了ＩＤ /*
fFind=ON;
return;
}
n1 = n + N1;
for(i = ORG ; i < nb ; i++) {
if(ban[i] == NON) continue; /* そこにコマがない /*
for(j = ORG ; j < nMove[i] ; j++) {
if(ban[move[M1(i , j)]] != NON) continue; /* 移動先にコマがあった /*
ban[move[M1(i , j)]] = ban[i]; /* 移動先 /*
ban[i] = NON; /* 移動元 /*
if(i == pos) sub(n , move[M1(i , j)]); /* 前回と同じ手 /*
else sub(n1 , move[M1(i , j)]); /* 前回と異なる手 /*
ban[i] = ban[move[M1(i , j)]]; /* 移動元に戻す /*
ban[move[M1(i , j)]] = NON; /* 移動先をクリア /*
}
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：0
*****************************************************************************/*
int main(void)
{
int limit = N6; /* 探査する最大手数 /*
int i; /* ループの制御変数 /*
init();
while(fFind == OFF) {
limit++;
for(i = ORG ; i < np ; i++) min[i] = limit; /* 最小手数を初期化 /*
sub(ORG , SHOKI);
}
printf("解答：%d手\n" , min[endId]); /* 解答表示 /*
end();
return(EXIT_SUCCESS);
}
|
第140回（11月）整数解の怪
|
|
/******************************************************************************
Ｃマガジン電脳クラブ２００２年８月出題（整数解の怪）
*****************************************************************************/*
#include <stdio.h>
#include <math.h>
int main(void)
{
int m = 2 , n;
int xt , yt , u , v;
int x , y;
int m2 , n2; /* m2 = m^2 , n2 = n^2 /*
double v2; /* v2 = v^2 /*
while(1) {
m2 = m * m;
for(n = 1 ; n < m ; n++) {
n2 = n * n;
xt = 2 * m * n;
yt = m2 - n2;
u = m2 + n2;
v2 = (double)u * (double)u - (double)xt * (double)yt;
v = (int)sqrt(v2);
if((double)v * (double)v != v2) continue;
/* v2が平方数でなければ次へ /*
x = xt < yt ? xt : yt; /* xt,ytの内、小さい方をxとする /*
y = xt < yt ? yt : xt; /* xt,ytの内、大きい方をyとする /*
if(x * 15 == y * 8) continue; /* x=8k && y=15k は除外する /*
printf("x=%d y=%d u=%d v=%d\n" , x , y, u , v); /* 解答表示 /*
return(0); /* 終了 /*
}
m++;
}
}
|
第139回（10月）RUSH HOUR
|
|
/******************************************************************************
Ｃマガジン２００２年７月号 電脳クラブ
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define BX 6 /* 駐車場の横方向の長さ /*
#define BX1 7 /* BX + 1 /*
#define BY 6 /* 駐車場の縦方向の長さ /*
#define BY1 7 /* BY + 1 /*
#define N24 24 /* 遷移の最大値 /*
#define NYOKO 6 /* 横方向の車の数 /*
#define NYOKO1 5 /* NYOKO - 1 /*
#define NTATE 7 /* 縦方向の車の数 /*
#define NTATE1 6 /* NTATE - 1 /*
#define NX 5 /* 車Ｘの番号 /*
#define NB 2 /* ２分岐の２ /*
#define N4 4 /* 車Ｘが外に出られる時のＸ座標 /*
#define N1 1 /* 最小単位 /*
#define N2 2 /* ０オリジンで３番目 /*
#define N3 3 /* 車の長さの最大値 /*
#define N0 0 /* 原点 /*
typedef struct {
int x; /* 車の始点のＸ座標 /*
int y; /* 車の始点のＹ座標 /*
int len; /* 車の長さ /*
char name; /* 車の名前 /*
} CARR;
CARR ax[] = { 1,0,2,'A' , 4,4,2,'G' , 0,5,2,'H' , 3,5,2,'I' ,
0,3,3,'L' , 3,2,2,'X'};/* 横方向の車の定義 /*
CARR ay[] = { 4,0,2,'B' , 1,1,2,'C' , 2,1,2,'D' , 3,3,2,'E' ,
2,4,2,'F' , 0,0,3,'J' , 5,1,3,'K'}; /* 縦方向の車の定義 /*
int b1[BY][BX]; /* 駐車場 /*
int nPat = N0; /* パターンの数 /*
typedef struct {
int id; /* パターンのＩＤ /*
int next[N24]; /* 次のパターン /*
int nNext; /* 次のパターンの数 /*
int rec; /* そのパターンにたどり着いた手数 /*
int fEnd; /* 終了フラグ /*
} PAT;
PAT *pat;
typedef struct {
int x[NYOKO]; /* 横方向の車の始点の移動中Ｘ座標 /*
int y[NTATE]; /* 縦方向の車の始点の移動中Ｙ座標 /*
} T1;
T1 t1;
int min; /* 最小手数 /*
/******************************************************************************
機能：パターン表示
引数：
id (I) : パターンのＩＤ
戻り値：なし
*****************************************************************************/*
void dispZ(int id)
{
int x , y;
int i , j; /* ループの制御変数 /*
for(y = N0 ; y < BY ; y++) { /* 描画する駐車場をクリア /*
for(x = N0 ; x < BX ; x++) b1[y][x] = ' ';
}
for(i = NTATE1 ; i >= N0 ; i--) {
y = id % (BY1 - ay[i].len); /* 縦方向の車の始点Ｙ座標を求める /*
for(j = N0 ; j < ay[i].len ; j++) b1[y + j][ay[i].x] = ay[i].name;
id /= (BY1 - ay[i].len);
}
for(i = NYOKO1 ; i >= N0 ; i--) {
x = id % (BX1 - ax[i].len); /* 横方向の車の始点Ｘ座標を求める /*
for(j = N0 ; j < ax[i].len ; j++) b1[ax[i].y][x + j] = ax[i].name;
id /= (BX1 - ax[i].len);
}
for(y = N0 ; y < BY ; y++) { /* 表示 /*
for(x = N0 ; x < BX ; x++) printf("%c" , b1[y][x]);
printf("\n");
}
}
/******************************************************************************
機能：各車の始点座標からＩＤを求める
引数：
t1 (i) 各車の座標
戻り値：ＩＤ
*****************************************************************************/*
int getId(T1 t1)
{
int id = N0;
int i; /* ループの制御変数 /*
for(i = N0 ; i < NYOKO ; i++) /* 横方向 /*
id = id * (BX1 - ax[i].len) + t1.x[i];
for(i = N0 ; i < NTATE ; i++) /* 縦方向 /*
id = id * (BY1 - ay[i].len) + t1.y[i];
return(id);
}
/******************************************************************************
機能：ＩＤから添え字番号を二分岐探査で求める。
引数：
ID (I) : ＩＤ
戻り値：添え字番号
*****************************************************************************/*
int search(int id)
{
int ps , pe , pm;
ps = N0;
pe = nPat - N1;
while(pe - ps > N1) {
pm = (ps + pe) / NB;
if(pat[pm].id < id) ps = pm;
else if(pat[pm].id == id) return(pm);
else pe = pm;
}
if(pat[ps].id == id) return(ps);
if(pat[pe].id == id) return(pe);
printf("program error\n");
exit(1);
}
int mode = OFF; /* OFF:パターンの数だけ求める ON:遷移を求める /*
/******************************************************************************
機能：縦方向の車を動かす。
引数：
n (I) : 縦方向の車の順番
戻り値：なし
*****************************************************************************/*
void tateMove(int n)
{
int y;
int i , j , k; /* ループの制御変数 /*
for(y = N0 ; y < BY1 - ay[n].len ; y++) {
if(b1[y][ay[n].x] == ON) continue; /* 他の車がいる /*
if(b1[y + 1][ay[n].x] == ON) continue; /* 他の車がいる /*
if(ay[n].len == N3) { /* 他の車がいる /*
if(b1[y + N2][ay[n].x] == ON) continue;
}
for(i = N0 ; i < ay[n].len ; i++) b1[y + i][ay[n].x] = ON;
t1.y[n] = y;
if(n == NTATE1) { /* 全部動かし終わったら /*
if(mode == ON) { /* 遷移を求める場合 /*
pat[nPat].id = getId(t1);
pat[nPat].nNext = N0;
for(j = N0 ; j < NYOKO ; j++) {
for(k = N0 ; k < ax[j].len ; k++)
b1[ax[j].y][t1.x[j] + k] = OFF;
k = N1; /* 横方向の車を負の方向に動かす /*
while(ON) {
if(t1.x[j] - k < N0) break;
if(b1[ax[j].y][t1.x[j] - k] == ON) break;
t1.x[j] -= k;
pat[nPat].next[pat[nPat].nNext] = getId(t1);
pat[nPat].nNext++;
t1.x[j] += k;
k++;
}
k = N1; /* 横方向の車を正の方向に動かす /*
while(ON) {
if(t1.x[j] + k + ax[j].len > BX) break;
if(b1[ax[j].y][t1.x[j] + k + ax[j].len - N1] == ON)
break;
t1.x[j] += k;
pat[nPat].next[pat[nPat].nNext] = getId(t1);
pat[nPat].nNext++;
t1.x[j] -= k;
k++;
}
for(k = N0 ; k < ax[j].len ; k++)
b1[ax[j].y][t1.x[j] + k] = ON;
}
for(j = N0 ; j < NTATE ; j++) {
for(k = N0 ; k < ay[j].len ; k++)
b1[t1.y[j] + k][ay[j].x] = OFF;
k = N1; /* 縦方向の車を負の方向に動かす /*
while(ON) {
if(t1.y[j] - k < N0) break;
if(b1[t1.y[j] - k][ay[j].x] == ON) break;
t1.y[j] -= k;
pat[nPat].next[pat[nPat].nNext] = getId(t1);
pat[nPat].nNext++;
t1.y[j] += k;
k++;
}
k = N1; /* 縦方向の車を正の方向に動かす /*
while(ON) {
if(t1.y[j] + k + ay[j].len > BY) break;
if(b1[t1.y[j] + k + ay[j].len - N1][ay[j].x] == ON)
break;
t1.y[j] += k;
pat[nPat].next[pat[nPat].nNext] = getId(t1);
pat[nPat].nNext++;
t1.y[j] -= k;
k++;
}
for(k = N0 ; k < ay[j].len ; k++)
b1[t1.y[j] + k][ay[j].x] = ON;
}
if(t1.x[NX] == N4) pat[nPat].fEnd = ON;
else pat[nPat].fEnd = OFF;
}
nPat++;
}
else tateMove(n + N1);
for(i = N0 ; i < ay[n].len ; i++) b1[y + i][ay[n].x] = OFF;
}
}
/******************************************************************************
機能：横方向の車を動かす。
引数：
n (I) : 横方向の車の順番
戻り値：なし
*****************************************************************************/*
void yokoMove(int n)
{
int x , y;
int i; /* ループの制御変数 /*
y = ax[n].y;
for(x = N0 ; x < BX1 - ax[n].len ; x++) {
if(b1[ax[n].y][x] == ON) continue; /* 他の車がいる /*
if(b1[ax[n].y][x + N1] == ON) continue; /* 他の車がいる /*
if(ax[n].len == N3) { /* 他の車がいる /*
if(b1[ax[n].y][x + N2] == ON) continue;
}
for(i = N0 ; i < ax[n].len ; i++) b1[ax[n].y][x + i] = ON;
t1.x[n] = x;
if(n == NYOKO1) tateMove(N0); /* 横方向が終わったら縦方向 /*
else yokoMove(n + N1); /* 次の横方向の車 /*
for(i = N0 ; i < ax[n].len ; i++) b1[ax[n].y][x + i] = OFF;
}
}
int *hId1; /* ここまで辿ってきたＩＤ /*
int *hId2; /* 最小手数で辿ってきたＩＤ /*
/******************************************************************************
機能：解を求める再帰ルーチン
引数：
n (I) : パターンの添え字番号
tesu (I) : ここまでの手数
戻り値：なし
*****************************************************************************/*
void subM(int n , int tesu)
{
int i; /* ループの制御変数 /*
if(tesu >= pat[n].rec) return;
pat[n].rec = tesu;
hId1[tesu] = n;
if(pat[n].fEnd == ON) {
if(tesu < min) {
min = tesu;
for(i = N0 ; i < tesu + N1 ; i++) hId2[i] = hId1[i];
}
return;
}
for(i = N0 ; i < pat[n].nNext ; i++) subM(pat[n].next[i] , tesu + 1);
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：０
*****************************************************************************/*
int main(void)
{
int x , y;
int i , j; /* ループの制御変数 /*
int n;
T1 t1;
for(i = N0 ; i < NYOKO ; i++) t1.x[i] = ax[i].x;
for(i = N0 ; i < NTATE ; i++) t1.y[i] = ay[i].y;
for(y = N0 ; y < BY ; y++) {
for(x = N0 ; x < BX ; x++) b1[y][x] = OFF;
}
yokoMove(N0); /* パターンの数を求める /*
pat = (PAT *)malloc(sizeof(PAT) * nPat);
if(pat == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(1);
}
mode = ON;
nPat = N0;
yokoMove(N0); /* 遷移先のＩＤを求める /*
hId1 = (int *)malloc(sizeof(int) * nPat);
if(hId1 == NULL) {
free(pat);
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(N1);
}
hId2 = (int *)malloc(sizeof(int) * nPat);
if(hId2 == NULL) {
free(pat);
free(hId1);
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(N1);
}
for(i = N0 ; i < nPat ; i++) { /* 遷移先のＩＤを添え字番号に変える /*
pat[i].rec = nPat;
for(j = N0 ; j < pat[i].nNext ; j++) {
pat[i].next[j] = search(pat[i].next[j]);
}
}
n = search(getId(t1));
min = nPat;
subM(n , N0);
printf("解答:%d\n" , min);
for(i = N0 ; i < min + N1 ; i++) {
printf("--- %d手 ---\n" , i);
dispZ(pat[hId2[i]].id);
}
free(pat); /* 領域開放 /*
free(hId1);
free(hId2);
return(N0);
}
|
第137回（8月）Ultimate Instant Insanity
|
|
/******************************************************************************
Ｃマガジン２００２年５月号電脳クラブ出題
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define COL_R 0 /* 赤 /*
#define COL_G 1 /* 緑 /*
#define COL_B 2 /* 青 /*
#define COL_W 3 /* 白 /*
#define COL_Y 4 /* 黄 /*
#define N3 3 /* ３次元 /*
#define N4 4 /* さいころの上下を除いた面の数 /*
#define N5 5 /* さいころの数 /*
#define N6 6 /* さいころの面の数 /*
#define N12 12 /* さいころの置き方の数の半分 /*
#define N24 24 /* さいころの置き方の数 /*
static int t1[][N4] = { /* 上下固定にした時の周りのパターン /*
1 , 3 , 4 , 5 , /* 0と2を固定。番号の対応はdice参照 /*
0 , 3 , 2 , 5 , /* 1と4を固定 /*
0 , 1 , 2 , 4}; /* 3と5を固定 /*
static int dice[][N6] = {
COL_R , COL_Y , COL_B , COL_G , COL_R , COL_W, /* 0 1 2 /*
COL_Y , COL_R , COL_W , COL_G , COL_Y , COL_B, /* 3 /*
COL_R , COL_G , COL_Y , COL_G , COL_B , COL_W, /* 4 /*
COL_G , COL_W , COL_R , COL_B , COL_B , COL_Y, /* 5 /*
COL_W , COL_Y , COL_B , COL_R , COL_G , COL_W
};
int t2[N24][N4]; /* さいころの置き方 /*
int f1[N4][N5]; /* 色の使用済みフラグ /*
int count = 0; /* 通りの数 /*
/******************************************************************************
機能：初期化
引数：なし
戻り値：なし
*****************************************************************************/*
void init(void)
{
int i0 , i1 , i2; /* ループの制御変数 /*
int n = 0;
for(i0 = 0 ; i0 < N4 ; i0++) {
for(i1 = 0 ; i1 < N3 ; i1++) {
for(i2 = 0 ; i2 < N4 ; i2++) {
t2[n][i2] = t1[i1][(i0 + i2) % N4]; /* 正回り /*
t2[n + N12][i2] = t1[i1][(i0 - i2 + N4) % N4]; /* 逆回り /*
}
n++;
}
for(i1 = 0 ; i1 < N5 ; i1++) f1[i0][i1] = OFF; /* 使用済をオフに /*
}
}
/******************************************************************************
機能：再帰関数
引数：
(1) n (I) 何番目のさいころか（０オリジン）
戻り値：なし
*****************************************************************************/*
void sub(int n)
{
int i , j; /* ループの制御変数 /*
for(i = 0 ; i < N24 ; i++) {
if(f1[0][dice[n][t2[i][0]]] == ON) continue; /* 既出色ならスキップ /*
if(f1[1][dice[n][t2[i][1]]] == ON) continue; /* 既出色ならスキップ /*
if(f1[2][dice[n][t2[i][2]]] == ON) continue; /* 既出色ならスキップ /*
if(f1[3][dice[n][t2[i][3]]] == ON) continue; /* 既出色ならスキップ /*
for(j = 0 ; j < N4 ; j++) f1[j][dice[n][t2[i][j]]] = ON; /* 既出 /*
if(n < 4) sub(n + 1); /* 次のさいころへ /*
else count++; /* ５個めならカウントアップ /*
for(j = 0 ; j < N4 ; j++) f1[j][dice[n][t2[i][j]]] = OFF; /* 戻す /*
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：0
*****************************************************************************/*
int main(void)
{
int i , j; /* ループの制御変数 /*
init(); /* 初期化 /*
for(i = 0 ; i < N3 ; i++) {
for(j = 0 ; j < N4 ; j++) f1[j][dice[0][t2[i][j]]] = ON; /* 既出 /*
sub(1); /* 次のさいころへ /*
for(j = 0 ; j < N4 ; j++) f1[j][dice[0][t2[i][j]]] = OFF; /* 戻す /*
}
printf("%d\n" , count); /* 解表示 /*
return(0);
}
|
第135回（6月）Ｉトロミノ
|
|
/******************************************************************************
Ｃマガジン２００２年３月号電脳クラブ出題 Ｉトロミノ
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define YSIZE 8 /* 盤のＹ方向の長さ /*
#define XSIZE 12 /* 盤のＸ方向の長さ /*
#define N32 32 /* 使用するトロミノの数 /*
#define AKI -1 /* 空いている（未使用）状態 /*
typedef struct {
int b1[YSIZE][XSIZE];
} BAN;
typedef struct {
int fx;
int fy;
} FXY;
int b1[YSIZE][XSIZE]; /* 盤 /*
BAN *b2 = NULL; /* 既出パターン /*
int nb2 = 0; /* 既出パターンの数 /*
int xsize1; /* 盤のＸ方向の大きさ−１ /*
int ysize1; /* 盤のＹ方向の大きさ−１ /*
int xsize2; /* 盤のＸ方向の大きさ−２ /*
int ysize2; /* 盤のＹ方向の大きさ−２ /*
/******************************************************************************
機能：既出パターンかどうか、鏡像チェックする。
引数：なし
戻り値：なし
*****************************************************************************/*
void check(void)
{
int i , j , k; /* ループの制御変数 /*
int x , y; /* 反転前座標 /*
int x1 , y1; /* 鏡像化による反転後座標 /*
static FXY fxy[] = {OFF,OFF , ON,OFF , OFF,ON}; /* 鏡像パターン /*
int a1[N32]; /* 反転後のＩトロミノ番号の一致チェック /*
for(i = 0 ; i < nb2 ; i++) {
for(k = 0 ; k < sizeof(fxy) / sizeof(fxy[1]) ; k++) {
for(j = 0 ; j < N32 ; j++) a1[j] = AKI;
for(y = 0 ; y < YSIZE ; y++) {
y1 = fxy[k].fy ? y : ysize1 - y;
for(x = 0 ; x < XSIZE ; x++) {
x1 = fxy[k].fx ? x : xsize1 - x;
if(a1[b1[y][x]] == AKI) {
a1[b1[y][x]] = b2[i].b1[y1][x1];
}
else if(a1[b1[y][x]] != b2[i].b1[y1][x1]) break;
}
if(x != XSIZE) break;
}
if(y == YSIZE) return;
}
}
b2 = (BAN *)realloc(b2 , sizeof(BAN) * (nb2 + 1));
if(b2 == NULL) {
fprintf(stderr , "realloc error at %d\n" , __LINE__);
exit(1);
}
for(y = 0 ; y < YSIZE ; y++) { /* 新パターンを格納 /*
for(x = 0 ; x < XSIZE ; x++) {
b2[nb2].b1[y][x] = b1[y][x];
}
}
nb2++;
return;
}
/******************************************************************************
機能：再帰関数
引数：
x (I) Ｘ座標
y (I) Ｙ座標
n (I) 置く板が何枚目かという数（０オリジン）
戻り値：なし
*****************************************************************************/*
void sub(int x , int y , int n)
{
int x1 , y1; /* 次の座標 /*
x1 = x + 1;
y1 = y;
if(x1 == XSIZE) {
x1 = 0;
y1++;
if(y1 == YSIZE) {
check();
return;
}
}
if(b1[y][x] != AKI) { /* 既に置かれていたら次へ /*
sub(x1 , y1 , n);
return;
}
if(x > 0 && y > 0) { /* 十字型継ぎ目チェック /*
if(b1[y][x - 1] != b1[y - 1][x - 1] &&
b1[y - 1][x] != b1[y - 1][x - 1]) return;
}
if(x < xsize2) { /* ＩトロミノをＸ方向に置く /*
if(b1[y][x + 1] == AKI && b1[y][x + 2] == AKI) {
b1[y][x] = b1[y][x1] = b1[y][x + 2] = n;
sub(x1 , y1 , n + 1);
b1[y][x] = b1[y][x1] = b1[y][x + 2] = AKI;
}
}
if(y < ysize2) { /* ＩトロミノをＹ方向に置く /*
if(b1[y + 1][x] == AKI && b1[y + 2][x] == AKI) {
b1[y][x] = b1[y + 1][x] = b1[y + 2][x] = n;
sub(x1 , y1 , n + 1);
b1[y][x] = b1[y + 1][x] = b1[y + 2][x] = AKI;
}
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：１
*****************************************************************************/*
int main(void)
{
int x , y; /* ループの制御変数 /*
for(y = 0 ; y < YSIZE ; y++) {
for(x = 0 ; x < XSIZE ; x++) b1[y][x] = AKI;
}
xsize1 = XSIZE - 1; /* 変数セット /*
ysize1 = YSIZE - 1;
xsize2 = XSIZE - 2;
ysize2 = YSIZE - 2;
b2 = (BAN *)malloc(sizeof(BAN));
if(b2 == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(1);
}
sub(0 , 0 , 0); /* 座標(0,0)から始める /*
printf("%d\n" , nb2);
free(b2);
return(0);
}
|
第134回（5月）３乗数の和
|
|
/******************************************************************************
Ｃマガジン２００２年２月出題 電脳クラブ ３乗数の和
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int x0 , y0 = 1 , y1 , x1 , y2 , x2; /* １〜３組の小数、大数 /*
int s0 , s1; /* 和 /*
int yp0 , xp1 , xp2; /* x0,x1,x2の３乗数 /*
int min = 2147483647; /* 解の最小値。初期値はint型の最大値 /*
int minx0 , miny0 , minx1 , miny1 , minx2 , miny2; /* 解の候補 /*
yp0 = y0 * y0 * y0;
while(yp0 < min) {
for(x0 = 1 ; x0 <= y0 ; x0++) { /* １組目の小数 /*
s0 = x0 * x0 * x0 + yp0; /* １組目の和 /*
y1 = y0 + 1; /* ２組の大数 /*
for(x1 = x0 - 1 ; x1 > 1 ; x1--) { /* ２組目の小数 /*
xp1 = x1 * x1 * x1;
s1 = xp1 + y1 * y1 * y1; /* ２組目の和 /*
while(s1 <= s0) {
if(s1 == s0) {
y2 = y1 + 1; /* ３組の大方 /*
for(x2 = x1 - 1 ; x2 > 0 ; x2--) { /* ３組目の小数 /*
xp2 = x2 * x2 * x2;
s1 = xp2 + y2 * y2 * y2; /* ３組目の和 /*
while(s1 <= s0) {
if(s1 == s0) {
if(s0 < min) { /* 最小なら候補に格納 /*
min = s0;
minx0 = x0;
miny0 = y0;
miny1 = y1;
minx1 = x1;
miny2 = y2;
minx2 = x2;
}
}
y2++;
s1 = xp2 + y2 * y2 * y2; /* ３組目の和 /*
}
}
break;
}
y1++;
s1 = xp1 + y1 * y1 * y1; /* ２組目の和 /*
}
}
}
y0++; /* １組の大数 /*
yp0 = y0 * y0 * y0;
}
printf("%d^3 + %d^3 = " , minx2 , miny2); /* ３組目 /*
printf("%d^3 + %d^3 = " , minx1 , miny1); /* ２組目 /*
printf("%d^3 + %d^3 = " , minx0 , miny0); /* １組目 /*
printf("%d\n" , min); /* 和 /*
return(1);
}
|
第133回（4月）見た目は月並みですが
|
|
/******************************************************************************
Ｃマガジン２００２年１月号電脳クラブ（見た目は月並みですが）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define YOKO 0 /* 横方向 /*
#define TATE 1 /* 縦方向 /*
#define XY(x , y) ((y) * nxy + (x)) /* ２次元座標を１次元に変換 /*
static char *mon[] = { /* 月の名称 /*
"JANUARY" , "FEBRUARY" , "MARCH" , "APRIL" ,
"MAY" , "JUNE" , "JULY" , "AUGUST" ,
"SEPTEMBER" , "OCTOBER" ,"NOVEMBER" , "DECEMBER"};
typedef struct {
int monNo; /* 月の番号 /*
int x; /* 始点Ｘ座標 /*
int y; /* 始点Ｙ座標 /*
int hoko; /* 置いてある方向 /*
} MM;
typedef struct {
int monNo; /* あちらの月の番号 /*
int x; /* こちらの交差座標 /*
int y; /* あちらの交差座標 /*
} JOIN;
typedef struct {
int x1; /* 最小Ｘ座標 /*
int y1; /* 最小Ｙ座標 /*
int x2; /* 最大Ｘ座標 /*
int y2; /* 最大Ｙ座標 /*
} AREA;
int nMon; /* 月の数 /*
MM *mm;
JOIN **join; /* 各月間の交差状況 /*
AREA minArea; /* 最小範囲 /*
int *lenm1; /* 月の名称の長さ /*
char *b1; /* 盤（マスごとにアルファベットをセット） /*
int *b2; /* 盤（マスごとに使用する月の数をセット） /*
char *b3; /* 盤（最小パターン） /*
int *fUsed; /* 月使用済みフラグ /*
int min; /* 面積の最小値 /*
int *nJoin; /* 交差状況の数 /*
int nxy = 0; /* 盤の縦、横それぞれの大きさ /*
/******************************************************************************
機能：月を１つ盤に置く
引数：
(1) n (I) 何番目か
(2) monNo (I) 置く月の番号
(3) x (I) 置く月の始点Ｘ座標
(4) y (I) 置く月の始点Ｙ座標
(5) hoko (I) YOKO:横方向、TATE:縦方向
(6) area (O) 範囲
戻り値：なし
*****************************************************************************/*
void set(int n , int monNo , int x , int y , int hoko , AREA *area)
{
int i;
int len;
len = lenm1[monNo];
if(hoko == YOKO) { /* 横方向 /*
for(i = 0 ; i < len ; i++) {
b1[XY(x + i , y)] = *(mon[monNo] + i); /* 文字を置く /*
b2[XY(x + i , y)]++; /* カウントアップ /*
}
if(x < area->x1) area->x1 = x; /* Ｘ座標最小値を更新 /*
if(x + len > area->x2) area->x2 = x + len; /* Ｘ座標最大値を更新 /*
}
else { /* 縦方向 /*
for(i = 0 ; i < len ; i++) {
b1[XY(x , y + i)] = *(mon[monNo] + i); /* 文字を置く /*
b2[XY(x , y + i)]++; /* カウントアップ /*
}
if(y < area->y1) area->y1 = y; /* Ｙ座標最小値を更新 /*
if(y + len > area->y2) area->y2 = y + len; /* Ｙ座標最大値を更新 /*
}
mm[n].monNo = monNo;
mm[n].x = x;
mm[n].y = y;
mm[n].hoko = hoko;
fUsed[monNo] = ON; /* 使用済みフラグをセット /*
}
/******************************************************************************
機能：月を１つ盤から取る
引数：
(1) monNo (I) 取る月の番号
(2) x (I) 取る月の始点Ｘ座標
(3) y (I) 取る月の始点Ｙ座標
(4) hoko (I) YOKO:横方向、TATE:縦方向
戻り値：なし
*****************************************************************************/*
void unset(int monNo , int x , int y , int hoko)
{
int i;
int len;
len = lenm1[monNo];
if(hoko == YOKO) { /* 横方向 /*
for(i = 0 ; i < len ; i++) {
b2[XY(x + i , y)]--; /* カウントダウン /*
}
}
else { /* 縦方向 /*
for(i = 0 ; i < len ; i++) {
b2[XY(x , y + i)]--; /* カウントダウン /*
}
}
fUsed[monNo] = OFF; /* 使用済みフラグを解除 /*
}
/******************************************************************************
機能：月を盤に置けるか調べる
引数：
(1) monNo (I) 月の番号
(2) x (I) 月の始点Ｘ座標
(3) y (I) 月の始点Ｙ座標
(4) hoko (I) YOKO:横方向、TATE:縦方向
戻り値：OFF:置けない、ON:置ける
*****************************************************************************/*
int okeruka(int monNo , int x , int y , int hoko)
{
int i;
int len;
len = lenm1[monNo];
if(hoko == YOKO) { /* 横方向 /*
for(i = 0 ; i < len ; i++) {
if(b2[XY(x + i , y)] == 0) continue; /* 未使用 /*
if(b1[XY(x + i , y)] == *(mon[monNo] + i)) continue; /* 同じ /*
return(OFF); /* 他の文字で使用済みなので置けない /*
}
}
else { /* 縦方向 /*
for(i = 0 ; i < len ; i++) {
if(b2[XY(x , y + i)] == 0) continue; /* 未使用 /*
if(b1[XY(x , y + i)] == *(mon[monNo] + i)) continue; /* 同じ /*
return(OFF); /* 他の文字で使用済みなので置けない /*
}
}
return(ON); /* 置ける /*
}
/******************************************************************************
機能：再帰関数
引数：
(1) n (I) 何番目か
(2) p1 (I) 交差調査済みの月
(3) p2 (I) 月の中で交差調査済みの番号
(4) area (I) 月を置いた範囲
戻り値：なし
*****************************************************************************/*
void sub(int n , int p1 , int p2 , AREA area)
{
int f1;
int x , y;
AREA nxtArea;
int s;
int curMonNo; /* 現在の月の番号 /*
int nxtMonNo; /* 次の月の番号 /*
int hoko; /* 月の方向 /*
s = (area.x2 - area.x1) * (area.y2 - area.y1); /* 面積を計算する /*
if(min <= s) return; /* 既最小値を越えたら探査中止 /*
if(n == nMon) { /* １２個置いたら /*
min = s;
for(y = area.y1 ; y < area.y2 ; y++) {
for(x = area.x1 ; x < area.x2 ; x++) {
if(b2[XY(x , y)] > 0) b3[XY(x , y)] = b1[XY(x , y)];
else b3[XY(x , y)] = ' ';
}
}
minArea.x1 = area.x1;
minArea.y1 = area.y1;
minArea.x2 = area.x2;
minArea.y2 = area.y2;
return;
}
while(p1 < n) {
curMonNo = mm[p1].monNo; /* 現在の月 /*
hoko = TATE - mm[p1].hoko; /* 次の月の方向は現在と反対 /*
while(p2 < nJoin[curMonNo]) {
nxtMonNo = (*(join + curMonNo) + p2)->monNo; /* 次の月の候補 /*
if(fUsed[nxtMonNo] == OFF) { /* 候補が未使用ならば /*
if(mm[p1].hoko == YOKO) { /* 横方向 /*
x = mm[p1].x + (*(join + curMonNo) + p2)->x; /* 交差Ｘ /*
y = mm[p1].y - (*(join + curMonNo) + p2)->y; /* 交差Ｙ /*
}
else { /* 縦方向 /*
x = mm[p1].x - (*(join + curMonNo) + p2)->y; /* 交差Ｘ /*
y = mm[p1].y + (*(join + curMonNo) + p2)->x; /* 交差Ｙ /*
}
f1 = okeruka(nxtMonNo , x , y , hoko); /* 置けるか判定 /*
if(f1 == ON) { /* もし置けるならば /*
nxtArea.x1 = area.x1;
nxtArea.y1 = area.y1;
nxtArea.x2 = area.x2;
nxtArea.y2 = area.y2;
set(n , nxtMonNo , x , y , hoko , &nxtArea); /* 置く /*
sub(n + 1 , p1 , p2 + 1 , nxtArea); /* 次へ /*
unset(nxtMonNo , x , y , hoko); /* 取る /*
}
}
p2++; /* 次の交差へ /*
}
p1++; /* 次の候補月へ /*
p2 = 0;
}
}
/******************************************************************************
機能：ｑｓｏｒｔ用の比較関数
引数：
(1) a (I) 比較対象のポインタ
(2) b (I) 比較対象のポインタ
戻り値：1:a<b、0:a==b、-1:a>b
*****************************************************************************/*
int cmp(const void *a , const void *b)
{
if (strlen(*((char **)a)) < strlen(*((char **)b))) return(1);
else if(strlen(*((char **)a)) == strlen(*((char **)b))) return(0);
else return(-1);
}
/******************************************************************************
機能：初期化関数
引数：なし
戻り値：なし
*****************************************************************************/*
void init(void)
{
int i , j;
int n;
int x , y;
nMon = sizeof(mon) / sizeof(mon[0]); /* 月の数 /*
qsort(mon , nMon , sizeof(char *) , cmp); /* 文字列が長い順にソート /*
mm = (MM *)malloc(sizeof(MM) * nMon);
lenm1 = (int *)malloc(sizeof(int) * nMon);
if(lenm1 == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(0);
}
fUsed = (int *)malloc(sizeof(int) * nMon);
if(fUsed == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(0);
}
nJoin = (int *)malloc(sizeof(int) * nMon);
if(nJoin == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(0);
}
for(i = 0 ; i < nMon ; i++) {
fUsed[i] = OFF;
lenm1[i] = strlen(mon[i]);
nxy += lenm1[i];
}
nxy = nxy * 2 - 1;
min = nxy * nxy;
b1 = (char *)malloc(sizeof(char) * min);
b2 = (int *)malloc(sizeof(int) * min);
b3 = (char *)malloc(sizeof(char) * min);
for(y = 0 ; y < nxy ; y++) {
for(x = 0 ; x < nxy ; x++) b2[XY(x , y)] = 0;
}
join = (JOIN **)malloc(sizeof(JOIN **) * nMon);
if(join == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(0);
}
for(i = 0 ; i < nMon ; i++) {
n = 0;
*(join + i) = (JOIN *)malloc(sizeof(JOIN));
if(*(join + i) == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(0);
}
for(j = 0 ; j < nMon ; j++) {
if(i == j) continue;
for(x = 0 ; x < lenm1[i] ; x++) {
for(y = 0 ; y < lenm1[j] ; y++) {
if(*(mon[i] + x) != *(mon[j] + y)) continue; /* 共有？ /*
*(join + i) =
(JOIN *)realloc(*(join + i) , sizeof(JOIN) * (n + 1));
if(*(join + i) == NULL) {
fprintf(stderr , "realloc error at %d\n" , __LINE__);
exit(0);
}
(*(join + i) + n)->monNo = j;
(*(join + i) + n)->x = x;
(*(join + i) + n)->y = y;
n++;
}
}
}
nJoin[i] = n;
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：０
*****************************************************************************/*
int main(void)
{
int x , y;
AREA area;
int i;
init();
area.x1 = nxy / 2;
area.y1 = area.x1;
area.x2 = area.x1 + 1;
area.y2 = area.x2;
set(0 , 0 , area.x1 , area.y1 , YOKO , &area); /* ９月をセット /*
sub(1 , 0 , 0 , area); /* 次へ /*
printf("面積：%d\n" , min); /* 解答表示 /*
for(y = minArea.y1 ; y < minArea.y2 ; y++) {
for(x = minArea.x1 ; x < minArea.x2 ; x++)
printf("%c" , b3[XY(x , y)]);
printf("\n");
}
free(mm);
free(lenm1);
free(fUsed);
free(nJoin);
free(b1);
free(b2);
free(b3);
for(i = 0 ; i < nMon ; i++) free(join[i]);
free(join);
return(0);
}
|
第132回（3月）素数で割り切る素数の和
|
|
/******************************************************************************
Ｃマガジン２００１年１２月号出題（素数で割り切る素数の和）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define N2 2 /* 最小の偶数素数 /*
#define N3 3 /* 最小の奇数素数 /*
#define NK 3 /* 求める解の数 /*
#define NN 10000 /* 素数の和を格納する配列の要素の最大値＋１ /*
int nSosu = 0; /* 素数の数 /*
int *sosu = NULL; /* 素数テーブル /*
/******************************************************************************
機能：素数がどうかチェックする。
引数：
(1) n (I) チェック対象の数
戻り値：OFF:非素数、ON:素数
*****************************************************************************/*
int check(int n)
{
int i; /* ループの制御変数 /*
for(i = 0 ; i < nSosu ; i++) {
if((n % sosu[i]) == 0) return(OFF); /* 素数で割りきれれば非素数 /*
if(sosu[i] * sosu[i] > n) break;
}
sosu = (int *)realloc(sosu , sizeof(int) * (nSosu + 1));
if(sosu == NULL) {
fprintf(stderr , "realloc error at %d\n" , __LINE__);
exit(0);
}
sosu[nSosu++] = n; /* 素数だったら素数テーブルに登録する /*
return(ON);
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：０
*****************************************************************************/*
int main(void)
{
int n0; /* 対象の数 /*
int n2 = N3; /* 対象の数に直近の素数候補 /*
int f0; /* n0が素数かどうかのフラグ OFF:非素数、ON:素数/*
int f2; /* n2が素数かどうかのフラグ OFF:非素数、ON:素数/*
int nd = 1; /* 素数の和を格納する配列の要素数 /*
int *sum; /* 素数の和 /*
int count = 0; /* 求まった解の数 /*
int t1; /* 割り算の余り /*
int i; /* ループの制御変数 /*
sum = (int *)malloc(sizeof(int) * nd);
if(sum == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(0);
}
sum[0] = N2;
n0 = n2 + N2;
sosu = (int *)malloc(sizeof(int)); /* ←ご指摘箇所 /*
f2 = check(n2);
while(count < NK) { /* 解がNK個見つかるまでループする /*
f0 = check(n0); /* 対象の数が素数かどうかチェックする /*
if(f2 == ON) { /* 対象の数−２が素数なら加算する /*
sum[0] += n2;
for(i = 0 ; i < nd - 1 ; i++) {
sum[i + 1] += sum[i] / NN;
sum[i] %= NN;
}
if(sum[nd - 1] >= NN) { /* 和が納まらなくなったら領域を拡大する /*
sum = (int *)realloc(sum , sizeof(int) * (nd + 1));
if(sum == NULL) {
fprintf(stderr , "realloc error at %d\n" , __LINE__);
exit(0);
}
sum[nd] = sum[nd - 1] / NN;
sum[nd - 1] %= NN;
nd++;
}
}
if(f0 == ON) {
t1 = sum[nd - 1] % n0;
for(i = nd - 2 ; i >= 0 ; i--) t1 = (sum[i] + t1 * NN) % n0;
if(t1 == 0) { /* 割った余りがゼロなら /*
printf("%d\n" , n0); /* 解を表示 /*
count++;
}
}
n2 = n0;
f2 = f0;
n0 += 2;
}
free(sum);
free(sosu);
return(0);
}
|
第131回（2月）チェス盤の分割
|
|
/******************************************************************************
Ｃマガジン２００１年１１月号出題 チェス盤の分割
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define NON 0 /* どちらでもない状態 /*
#define BAN_A 1 /* ２片のうちのＡ /*
#define BAN_B 2 /* ２片のうちのＢ /*
#define NN 10 /* チェス盤の大きさ /*
int nx; /* NN - 2 /*
int ny; /* NN / 2 /*
int nx1; /* nx - 1 /*
int ny1; /* ny - 1 /*
int nxy2; /* NN * NN / 2 - NN /*
int nn1; /* NN - 1 /*
int b1[NN][NN]; /* チェス盤 BAN_A=Ａ片 BAN_B=Ｂ片 NON=どちらでもない /*
int b2[NN][NN]; /* チェス盤 OFF=未チェック ON=チェック済み /*
int count = 0; /* パターンの数 /*
/******************************************************************************
機能：チェックの再帰関数
自分と同じ片、あるいはまだ置いてない場所を辿り、端まで到達できるか？
引き数：
(1) x (I) : Ｘ座標
(2) y (I) : Ｙ座標
(3) p1 (I) : 相手の片の種類
(4) rx (I) : 到達すべきＸ座標
戻り値：OFF=駄目 ON=ＯＫ
*****************************************************************************/*
int check_sub(int x , int y , int p1 , int rx)
{
if(b1[y][x] == p1) return(OFF);
if(x == rx) return(ON); /* 自分の片へ達したら戻る /*
if(b2[y][x] == ON) return(OFF);
b2[y][x] = ON;
if(x > 0) { /* Ｘ座標を＋１して次へ /*
if(check_sub(x - 1 , y , p1 , rx) == ON) return(ON);
}
if(x < nx1) { /* Ｘ座標を−１して次へ /*
if(check_sub(x + 1 , y , p1 , rx) == ON) return(ON);
}
if(y > 0) { /* Ｙ座標を−１して次へ /*
if(check_sub(x , y - 1 , p1 , rx) == ON) return(ON);
}
if(y < nn1) { /* Ｙ座標を＋１して次へ /*
if(check_sub(x , y + 1 , p1 , rx) == ON) return(ON);
}
return(OFF);
}
/******************************************************************************
機能：題意を満たすかどうかのチェック
引き数：
(1) x (I) : Ｘ座標
(2) y (I) : Ｙ座標
(3) p1 (I) : 相手の片の種類
(4) rx (I) : 到達すべきＸ座標
戻り値：OFF=駄目 ON=ＯＫ
*****************************************************************************/*
int check(int x , int y , int p1 , int rx)
{
int x1 , y1; /* 座標 /*
for(y1 = 0 ; y1 < NN ; y1++) { /* チェス盤全体を未チェックにセット /*
for(x1 = 0 ; x1 < nx ; x1++) b2[y1][x1] = OFF;
}
return(check_sub(x , y , p1 , rx));
}
/******************************************************************************
機能：再帰関数
１箇所ずつ、ＡまたはＢをセットしていく。
引き数：
(1) x (I) : Ｘ座標
(2) y (I) : Ｙ座標
(3) f1 (I) 上下反転鏡像チェック済みフラグ OFF=未チェック ON=チェック済み
戻り値：なし
*****************************************************************************/*
void sub(int x , int y ,int f1)
{
int x2 , y2; /* 次の座標 /*
int x3; /* 座標 /*
int sts; /* 戻り値を格納 /*
if(x == 0 && f1 == OFF) { /* 上下反転鏡像チェック /*
for(x3 = 0 ; x3 < nx ; x3++) {
if(b1[y - 1][x3] == BAN_A && b1[y - 1][nx1 - x3] == BAN_A) {
f1 = ON;
break;
}
if(b1[y - 1][x3] == BAN_B && b1[y - 1][nx1 - x3] == BAN_B) return;
}
}
if(y == ny) { /* チェス盤が全て埋まったら題意を満たすかチェック /*
for(x3 = 0 ; x3 < nx ; x3++) {
if(b1[ny1][x3] == BAN_A) sts = check(x3 , ny1 , BAN_B , 0);
else sts = check(x3 , ny1 , BAN_A , nx1);
if(sts == OFF) return;
}
count++;
return;
}
x2 = x + 1; /* 次の手の座標を求める /*
y2 = y;
if(x2 == nx) {
x2 = 0;
y2++;
}
sts = ON;
b1[y][x] = BAN_A; /* その場所をＡ片にする（対照位置はＢ片） /*
b1[nn1 - y][nx1 - x] = BAN_B;
if(y > 0) { /* 置けるか（孤立するＢ片が存在するかチェック） /*
if(b1[y - 1][x] == BAN_B) sts = check(x , y - 1 , BAN_A , nx1);
}
if(sts == ON) sub(x2 , y2 , f1); /* Ａ片を置いて次へ /*
sts = ON;
b1[y][x] = BAN_B; /* その場所をＢ片にする（対照位置はＡ片） /*
b1[nn1 - y][nx1 - x] = BAN_A;
if(y > 0) { /* 置けるか（孤立するＡ片が存在するかチェック） /*
if(b1[y - 1][x] == BAN_A) sts = check(x , y - 1 , BAN_B , 0);
}
if(sts == ON) sub(x2 , y2 , f1); /* Ｂ片を置いて次へ /*
b1[y][x] = b1[nn1 - y][nx1 - x] = NON; /* 元に戻す/*
}
/******************************************************************************
機能：メイン。チェス盤の初期化など
引き数：なし
戻り値：０
*****************************************************************************/*
int main(void)
{
int x , y; /* 座標 /*
nx = NN - 2; /* 定数の設定 /*
ny = NN / 2; /* 定数の設定 /*
nx1 = nx - 1; /* 定数の設定 /*
ny1 = ny - 1; /* 定数の設定 /*
nxy2 = (NN * NN) / 2 - NN; /* 定数の設定 /*
nn1 = NN - 1; /* 定数の設定 /*
for(y = 0 ; y < ny ; y++) { /* チェス盤の初期化 /*
for(x = 0 ; x < nx ; x++) {
b1[y][x] = b1[ny + y][x] = NON;
}
}
b1[0][0] = BAN_A;
b1[nn1][nx1] = BAN_B;
sub(1 , 0 , OFF);
printf("%d\n" , count); /* 解答表示 /*
return(0);
}
|
第130回（1月）こだ割り数
|
|
/* C MAGAZINE 2001.10電脳クラブ出題 こだ割り数 /*
#include <stdio.h>
#include <stdlib.h>
int max = -1; /* 最大値の桁数 /*
int *m1; /* 最大値 /*
#define N1 10 /* １０進法の１０ /*
#define N2 10000 /* N3 / N1 /*
#define N3 100000 /* ロング数の個々の要素の最大値＋１ /*
#define N5 5 /* ロング数の個々の要素の桁数 /*
/******************************************************************************
機能：再帰ルーチン
引数：
(1) s1 (I) ここまでの数（ｎ−１）桁
(2) n (I) 今回の桁数
戻り値：なし
*****************************************************************************/*
void sub(int *s1 , int n)
{
int i , j; /* ループの制御変数 /*
int *s2; /* ｎ桁の数 /*
int k; /* ｎ桁におけるロング数の要素の数 /*
int a; /* 余り /*
k = (n - 1) / N5;
s2 = (int *)malloc(sizeof(int) * (k + 1));
if(s2 == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
return;
}
if(((n - 1) % N5) == 0) s1[k] = 0; /* 要素数が増えた場合、０をセット /*
for(i = 0 ; i < N1 ; i++) { /* 最下位の桁追加（０〜９） /*
for(j = k ; j > 0 ; j--)
s2[j] = (s1[j] % N2) * N1 + s1[j - 1] / N2; /* １０倍する /*
s2[0] = (s1[0] % N2) * N1 + i; /* 最下位桁 /*
a = s2[k] % n;
for(j = k - 1 ; j >= 0 ; j--) a = (s2[j] + a * N3) % n;
if(a != 0) continue; /* 割り切れない場合にスキップ /*
if(n >= max) { /* 最大値だった場合の処理 /*
max = n;
m1 = (int *)realloc(m1 , sizeof(int) * (k + 1));
if(m1 == NULL) {
fprintf(stderr , "realloc error at %d\n" , __LINE__);
free(s2);
return;
}
for(j = 0 ; j < k + 1 ; j++) m1[j] = s2[j]; /* 解答を退避 /*
}
sub(s2 , n + 1);
}
free(s2);
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：０
*****************************************************************************/*
int main(void)
{
int i , j; /* ループの制御変数 /*
int k; /* ｎ桁におけるロング数の要素の数 /*
int d;
int s1[1];
m1 = (int *)malloc(sizeof(int)); /* 解答のロング数のメモリ確保 /*
if(m1 == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(0);
}
for(i = 1 ; i < N1 ; i++) {
s1[0] = i; /* 最上位桁の値（１〜９） /*
sub(s1 , 2);
}
k = (max - 1) / N5; /* 解答のロング数の要素の数 /*
printf("%d" , m1[k]);
for(i = k - 1 ; i >= 0 ; i--) {
d = N2;
for(j = 0 ; j < N5 ; j++) { /* ５桁ごとに解答表示 /*
printf("%1d" , (m1[i] / d) % N1);
d /= N1;
}
}
printf("\n");
free(m1);
return(0);
}
| | | | | | | | | |