#include #include #include #include #include #include // 内部定数 #define D_SIZE_MAX 200 // 最大1辺サイズ #define D_HEAP_MAX D_SIZE_MAX * D_SIZE_MAX // 最大ヒープ数 // 内部構造体 - ヒープ情報 typedef struct Heap { int miHP; // 体力 int miX, miY; // 位置 } Heap; // 内部変数 static FILE *szpFpI; // 入力 static int siSize; // 1辺サイズ static int siHP; // 初期体力 static int siOx, siOy; // オアシス位置 static int si2Desert[D_SIZE_MAX + 5][D_SIZE_MAX + 5]; // 砂漠 static int si2Done[D_SIZE_MAX + 5][D_SIZE_MAX + 5]; // 砂漠到着時体力 static Heap sz1Heap[D_HEAP_MAX]; // ヒープ static int siHCnt; // ヒープ数 // 内部変数 - テスト用 #ifdef D_TEST static int siRes; static FILE *szpFpA; #endif // ヒープ - 比較 - 体力降順 int fHeapCmp( int piNo1 // 配列番号1 0~ , int piNo2 // 配列番号2 0~ ) { // 体力降順 if (sz1Heap[piNo1].miHP < sz1Heap[piNo2].miHP) { return 1; } else if (sz1Heap[piNo1].miHP > sz1Heap[piNo2].miHP) { return -1; } return 0; } // ヒープ - 親子関係チェック // 戻り値:[>=0]:変更した子の配列番号 [-1]:変更なし int fHeapChk( int piPNo // 親の配列番号 0~ ) { int liRet; // 最小値 int liMNo = piPNo; // 左の子と比較 int liCNo = piPNo * 2 + 1; if (liCNo < siHCnt) { liRet = fHeapCmp(liMNo, liCNo); if (liRet == 1) { liMNo = liCNo; } } // 右の子と比較 liCNo = piPNo * 2 + 2; if (liCNo < siHCnt) { liRet = fHeapCmp(liMNo, liCNo); if (liRet == 1) { liMNo = liCNo; } } // 自分が最小値であるかチェック if (piPNo == liMNo) { return -1; } // 値の交換 Heap lzWork; memcpy(&lzWork, &sz1Heap[liMNo], sizeof(Heap)); memcpy(&sz1Heap[liMNo], &sz1Heap[piPNo], sizeof(Heap)); memcpy(&sz1Heap[piPNo], &lzWork, sizeof(Heap)); return liMNo; } // ヒープ - キュー追加 int fHeapEnqueue( int piHP // 体力 , int piX // 位置X , int piY // 位置Y ) { int liRet; // 末尾に追加 sz1Heap[siHCnt].miHP = piHP; sz1Heap[siHCnt].miX = piX; sz1Heap[siHCnt].miY = piY; siHCnt++; // 親子関係チェック int liNo = siHCnt - 1; while (1) { // 親の配列番号 liNo = (liNo - 1) / 2; // 親子関係チェック liRet = fHeapChk(liNo); if (liRet < 0) { break; } } return 0; } // ヒープ - キュー取得 int fHeapDequeue( Heap *pzpRet // 取得先 ) { // データ数 if (siHCnt < 1) { return -1; } // 取得 memcpy(pzpRet, &sz1Heap[0], sizeof(Heap)); siHCnt--; // データ数 if (siHCnt < 1) { return 0; } // 末尾を先頭へ memcpy(&sz1Heap[0], &sz1Heap[siHCnt], sizeof(Heap)); // 親子関係チェック int liNo = 0; while (liNo >= 0) { liNo = fHeapChk(liNo); } return 0; } // 移動 int fMove( int piHP // 体力 , int piX // 位置X , int piY // 位置Y ) { // 体力減少 piHP -= si2Desert[piY][piX]; if (piHP <= 0) { return -1; } // オアシス if (piX == siOx) { if (piY == siOy) { siOx = 0; siOy = 0; piHP *= 2; } } // 砂漠到着時体力 if (si2Done[piY][piX] >= piHP) { return -1; } si2Done[piY][piX] = piHP; // 到着チェック if (piX == siSize) { if (piY == siSize) { return 0; } } // キュー追加 fHeapEnqueue(piHP, piX, piY); return -1; } // 判定 int fJudge( ) { int liRet; // スタート地点へ fMove(siHP + si2Desert[1][1], 1, 1); while (1) { // キュー取得 Heap lzHeap; liRet = fHeapDequeue(&lzHeap); if (liRet != 0) { return -1; } // 右へ liRet = fMove(lzHeap.miHP, lzHeap.miX + 1, lzHeap.miY); if (liRet == 0) { break; } // 左へ liRet = fMove(lzHeap.miHP, lzHeap.miX - 1, lzHeap.miY); if (liRet == 0) { break; } // 下へ liRet = fMove(lzHeap.miHP, lzHeap.miX, lzHeap.miY + 1); if (liRet == 0) { break; } // 上へ liRet = fMove(lzHeap.miHP, lzHeap.miX, lzHeap.miY - 1); if (liRet == 0) { break; } } return 0; } // 実行メイン int fMain( int piTNo // テスト番号 1~ ) { int i, j, liRet; char lc1Buf[1024], lc1Out[1024]; // データ - 初期化 memset(si2Done, 0, sizeof(si2Done)); // 砂漠到着時体力 siHCnt = 0; // ヒープ数 // 入力 - セット #ifdef D_TEST sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo); szpFpI = fopen(lc1Buf, "r"); sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo); szpFpA = fopen(lc1Buf, "r"); siRes = 0; #else szpFpI = stdin; #endif // 1辺サイズ・初期体力・オアシス位置 - 取得 fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d%d%d%d", &siSize, &siHP, &siOx, &siOy); // 砂漠 - 初期化 for (i = 0; i <= siSize + 1; i++) { for (j = 0; j <= siSize + 1; j++) { si2Desert[i][j] = siHP * 2; } } // 砂漠 - 取得 for (i = 1; i <= siSize; i++) { for (j = 1; j <= siSize; j++) { fscanf(szpFpI, "%d", &si2Desert[i][j]); } fgets(lc1Buf, sizeof(lc1Buf), szpFpI); } // 判定 liRet = fJudge(); // 結果 - セット if (liRet == 0) { sprintf(lc1Out, "YES\n"); } else { sprintf(lc1Out, "NO\n"); } // 結果 - 表示 #ifdef D_TEST fgets(lc1Buf, sizeof(lc1Buf), szpFpA); if (strcmp(lc1Buf, lc1Out)) { siRes = -1; } #else printf("%s", lc1Out); #endif // 残データ有無 #ifdef D_TEST lc1Buf[0] = '\0'; fgets(lc1Buf, sizeof(lc1Buf), szpFpA); if (strcmp(lc1Buf, "")) { siRes = -1; } #endif // テストファイルクローズ #ifdef D_TEST fclose(szpFpI); fclose(szpFpA); #endif // テスト結果 #ifdef D_TEST if (siRes == 0) { printf("OK %d\n", piTNo); } else { printf("NG %d\n", piTNo); } #endif return 0; } int main() { #ifdef D_TEST int i; for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) { fMain(i); } #else fMain(0); #endif return 0; }