与えられたぷよぷよフィールドが19連鎖であることを証明する
とあるHP*1にて発見した問題。
久しぶりにCで書いたらSEGVで落ちまくり結局1時間弱かかってしまった。。。
問題
ゲーム「ぷよぷよ」で、フィールドの状態がテキストで与えられたとき、消える「ぷよ」を消して次のフィールドの状態を出力するプログラムを書け。 たとえば、色をG/Y/Rで表すとき(Green/Yellow/Red)、 GGR YGG であればGが消えて Y R になります。 また、このプログラムを使って次のフィールドを与えると19連鎖ののちすべてのぷよが消えることを確認し、消える途中の様子をあわせて提出すること。 GYRR RYYGYG GYGYRR RYGYRG YGYRYG GYRYRG YGYRYR YGYRYR YRRGRG RYGYGG GRYGYR GRYGYR GRYGYR ※１行目の"GYRR"の前には半角スペースが2つ入っている
バージョン１（思いつくがままに書いたバージョン）
塗りつぶしアルゴリズム(mark関数)が糞
#include <stdio.h> #include <stdlib.h> #include <string.h> char **input(int *w, int *h); void free_board(char **board, int h); void show(char **board, int w, int h); int mark(char **board, int w, int h); void del(char **board, int w, int h); char **input(int *w, int *h) { int ww =0, hh = 0, alloc_h = 10; char *p, **board = (char **)malloc(sizeof (char *) * alloc_h); char buf[256]; while (fgets(buf, 256, stdin) != NULL) { while (buf[strlen(buf) - 1] == '\n' || buf[strlen(buf) - 1] == '\r') buf[strlen(buf) - 1] = '\0'; if (ww == 0) { ww = strlen(buf); } else if (ww != strlen(buf)) { free_board(board, hh); return NULL; } board[hh] = strcpy((char *)malloc(ww + 1), buf); hh++; if (hh >= alloc_h) { alloc_h += 10; board = (char **)realloc(board, sizeof (char *) * alloc_h); } } *w = ww; *h = hh; return board; } void free_board(char **board, int h) { int i; for (i = 0; i < h; i++) { free(board[i]); } free(board); } void show(char **board, int w, int h) { int i; for (i = 0; i < w + 2; i++) putchar('-'); printf("\n"); for (i = 0; i < h; i++) { printf("|%s|\n", board[i]); } for (i = 0; i < w + 2; i++) putchar('-'); printf("\n"); } int mark(char **board, int w, int h) { int i, j, k, l, dels, count, total = 0; char c; for (i = 0; i < h; i++) { for (j = 0; j < w; j++) { c = board[i][j]; if (c == ' ' || c == '*') continue; board[i][j] = '%'; dels = 1; do { count = 0; for (k = 0; k < h; k++) { for (l = 0; l < w; l++) { if (board[k][l] != c) continue; if ( (k - 1 >= 0 && board[k - 1][l] == '%') || (k + 1 < h && board[k + 1][l] == '%') || (l - 1 >= 0 && board[k][l - 1] == '%') || (l + 1 < w && board[k][l + 1] == '%') ) { board[k][l] = '%'; count++; } } } dels += count; } while (count > 0); if (dels >= 4) { c = '*'; total += dels; } for (k = 0; k < h; k++) { for (l = 0; l < w; l++) { if (board[k][l] == '%') board[k][l] = c; } } } } return total; } void del(char **board, int w, int h) { int i, j, k, l; for (i = h - 1; i >= 0; i--) { for (j = 0; j < w; j++) { if (board[i][j] == '*') board[i][j] = ' '; if (board[i][j] == ' ') { for (k = i - 1; k >= 0; k--) { if (board[k][j] != ' ' && board[k][j] != '*') { board[i][j] = board[k][j]; if (board[i][j] == '*') board[i][j] = ' '; board[k][j] = ' '; break; } } } } } } int main(int argc, char **argv) { int i = 0, w, h; char **board = input(&w, &h); if (board == NULL) { exit(1); } show(board, w, h); while (mark(board, w, h) > 0) { printf("%d:\n", ++i); show(board, w, h); del(board, w, h); show(board, w, h); } free_board(board, h); return 0; }
塗りつぶしアルゴリズムをスタックを使ったバージョンにしたもの。5重ループが3重ループになりすっきり。108連鎖*2を与えた場合には10倍程度早くなった。
int mark(char **board, int w, int h) { int i, j, k, dels, total = 0, x, y; int *stack = (int *)malloc(sizeof (int) * w * h), sp; char c; for (i = 0; i < h; i++) { for (j = 0; j < w; j++) { c = board[i][j]; if (c == ' ' || c == '*') continue; dels = sp = 0; stack[dels++] = i * w + j; while (sp < dels) { x = stack[sp] % w; y = stack[sp] / w; board[y][x] = '%'; if (x - 1 >= 0 && board[y][x - 1] == c) stack[dels++] = y * w + x - 1; if (x + 1 < w && board[y][x + 1] == c) stack[dels++] = y * w + x + 1; if (y - 1 >= 0 && board[y - 1][x] == c) stack[dels++] = (y - 1) * w + x; if (y + 1 < h && board[y + 1][x] == c) stack[dels++] = (y + 1) * w + x; sp++; } if (dels >= 4) { c = '*'; total += dels; } for (k = 0; k < dels; k++) { board[stack[k] / w][stack[k] % w] = c; } } } free(stack); return total; }
最初からこれを書けなくなっているのは衰えている証拠かな。。
