結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2019-04-04 15:47:41 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 530 ms / 3,000 ms |
コード長 | 4,832 bytes |
コンパイル時間 | 736 ms |
コンパイル使用メモリ | 35,072 KB |
実行使用メモリ | 107,520 KB |
最終ジャッジ日時 | 2024-12-25 23:34:36 |
合計ジャッジ時間 | 4,960 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <float.h>#include <limits.h>#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>// 内部定数#define D_SIZE_MAX 3005 // 最大サイズ#define D_STACK_MAX D_SIZE_MAX * D_SIZE_MAX // 最大スタック数// 内部構造体 - スタック情報typedef struct Stack {int miX, miY; // 位置} Stack;// 内部変数static FILE *szpFpI; // 入力static int siW, siH; // 幅・高さstatic int si2Mass[D_SIZE_MAX][D_SIZE_MAX]; // マスstatic Stack sz1Stack[D_STACK_MAX]; // スタックstatic int siSCnt; // スタック数static int siSSNo; // スタック位置 - セットstatic int siSGNo; // スタック位置 - 取得// 内部変数 - テスト用#ifdef D_TESTstatic int siRes;static FILE *szpFpA;static int siTNo;#endif// 出力intfOut(char *pcpLine // <I> 1行){char lc1Buf[1024];#ifdef D_TESTfgets(lc1Buf, sizeof(lc1Buf), szpFpA);if (strcmp(lc1Buf, pcpLine)) {siRes = -1;}#elseprintf("%s", pcpLine);#endifreturn 0;}// スタック - セットintfStackSet(int piX // <I> 位置X, int piY // <I> 位置Y, int piH // <I> 高さ){// 高さsi2Mass[piX][piY] = piH;// スタック - セットsz1Stack[siSSNo].miX = piX;sz1Stack[siSSNo].miY = piY;// スタック数siSCnt++;// スタック位置 - セットif (siSSNo < D_STACK_MAX - 1) {siSSNo++;}else {siSSNo = 0;}return 0;}// スタック - 取得intfStackGet(Stack *pzpRet // <O> 取得値){// スタック数if (siSCnt < 1) {return -1;}siSCnt--;// 取得memcpy(pzpRet, &sz1Stack[siSGNo], sizeof(Stack));// スタック位置 - 取得if (siSGNo < D_STACK_MAX - 1) {siSGNo++;}else {siSGNo = 0;}return 0;}// 1マスintfMassOne(Stack *pzpStack // <I> スタック, int piX // <I> 移動方向X, int piY // <I> 移動方向Y, int piH // <I> 高さ){// 対象位置int liX = pzpStack->miX + piX;int liY = pzpStack->miY + piY;// 高さif (si2Mass[liX][liY] <= piH) {return 0;}// スタックfStackSet(liX, liY, piH);return 0;}// 実行メインintfMain(){int i, j;char lc1Buf[D_SIZE_MAX];// 幅・高さ - 取得fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d%d", &siH, &siW);// マス - 外側1for (i = 0; i <= siW + 3; i++) {si2Mass[i][0] = 0;si2Mass[i][siH + 3] = 0;}for (i = 1; i <= siH + 2; i++) {si2Mass[0][i] = 0;si2Mass[siW + 3][i] = 0;}// マス - 外側2for (i = 1; i <= siW + 2; i++) {fStackSet(i, 1, 0);fStackSet(i, siH + 2, 0);}for (i = 2; i <= siH + 1; i++) {fStackSet(1, i, 0);fStackSet(siW + 2, i, 0);}// マス - 取得for (i = 2; i <= siH + 1; i++) {fgets(lc1Buf, sizeof(lc1Buf), szpFpI);for (j = 0; j < siW; j++) {if (lc1Buf[j] == '#') { // 陸si2Mass[j + 2][i] = INT_MAX;}else { // 海fStackSet(j + 2, i, 0);}}}// マス - 更新for (i = 1; ; i++) {// スタック数でループint liSCnt = siSCnt;for (j = 0; j < liSCnt; j++) {// スタック - 取得Stack lzStack;fStackGet(&lzStack);// 8方向へセットfMassOne(&lzStack, 1, 0, i);fMassOne(&lzStack, -1, 0, i);fMassOne(&lzStack, 0, 1, i);fMassOne(&lzStack, 0, -1, i);fMassOne(&lzStack, 1, 1, i);fMassOne(&lzStack, 1, -1, i);fMassOne(&lzStack, -1, 1, i);fMassOne(&lzStack, -1, -1, i);}// スタックなしif (siSCnt < 1) {return i - 1;}}return 0;}// 1回実行intfOne(){int liRet;char lc1Buf[1024];// データ - 初期化siSCnt = 0; // スタック数siSSNo = 0; // スタック位置 - セットsiSGNo = 0; // スタック位置 - 取得// 入力 - セット#ifdef D_TESTsprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);szpFpI = fopen(lc1Buf, "r");sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);szpFpA = fopen(lc1Buf, "r");siRes = 0;#elseszpFpI = stdin;#endif// 実行メインliRet = fMain();// 結果 - セットsprintf(lc1Buf, "%d\n", liRet);// 結果 - 出力fOut(lc1Buf);// 残データ有無#ifdef D_TESTlc1Buf[0] = '\0';fgets(lc1Buf, sizeof(lc1Buf), szpFpA);if (strcmp(lc1Buf, "")) {siRes = -1;}#endif// テストファイルクローズ#ifdef D_TESTfclose(szpFpI);fclose(szpFpA);#endif// テスト結果#ifdef D_TESTif (siRes == 0) {printf("OK %d\n", siTNo);}else {printf("NG %d\n", siTNo);}#endifreturn 0;}// プログラム開始intmain(){#ifdef D_TESTint i;for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {siTNo = i;fOne();}#elsefOne();#endifreturn 0;}