#include #include #include #include #include #include #include // 内部定数 #define D_ON 1 // 汎用フラグ - ON #define D_OFF 0 // 汎用フラグ - OFF #define D_SIZE_MAX 3005 // 最大サイズ #define D_WAY_CNT 4 // 方向数 #define D_WAY_R 0 // 方向 - 右 #define D_WAY_L 1 // 方向 - 左 #define D_WAY_D 2 // 方向 - 下 #define D_WAY_U 3 // 方向 - 上 #define D_STACK_MAX D_SIZE_MAX // 最大スタック数 // 内部構造体 - 位置情報 typedef struct Pos { char mc1Con[D_WAY_CNT]; // 接続 char mcDone; // 処理済フラグ } Pos; // 内部構造体 - スタック情報 typedef struct Stack { int miX, miY; // 位置 } Stack; // 内部変数 static FILE *szpFpI; // 入力 static int si2Mx[D_SIZE_MAX][D_SIZE_MAX]; // 横移動[位置Y][位置X] static int si2My[D_SIZE_MAX][D_SIZE_MAX]; // 縦移動[位置X][位置Y] static int siW, siH; // 幅・高さ static Pos sz2Pos[D_SIZE_MAX][D_SIZE_MAX]; // 位置情報[位置X][位置Y] static Stack sz1Stack[D_STACK_MAX]; // スタック static int siSCnt; // スタック数 static int siSSNo; // スタック位置 - セット static int siSGNo; // スタック位置 - 取得 // 内部変数 - テスト用 #ifdef D_TEST static int siRes; static FILE *szpFpA; #endif // スタック - 追加 int fStackAdd( int piX // 位置X , int piY // 位置Y ) { // 処理済フラグ if (sz2Pos[piX][piY].mcDone != D_OFF) { return 0; } sz2Pos[piX][piY].mcDone = D_ON; // セット sz1Stack[siSSNo].miX = piX; sz1Stack[siSSNo].miY = piY; // スタック数 siSCnt++; // スタック位置 - セット if (siSSNo < D_STACK_MAX - 1) { siSSNo++; } else { siSSNo = 0; } return 0; } // スタック - 取得 int fStackGet( Stack *pzpRet // 取得値 ) { // スタック数 if (siSCnt < 1) { return -1; } siSCnt--; // 取得 memcpy(pzpRet, &sz1Stack[siSGNo], sizeof(Stack)); // スタック位置 - 取得 if (siSGNo < D_STACK_MAX - 1) { siSGNo++; } else { siSGNo = 0; } return 0; } // 最短距離 - 取得 int fGetMin( ) { int i, j, k; // スタック - 初期位置 fStackAdd(0, 0); // 最短距離 - セット int liLen = -1; for (i = 1; ; i++) { // スタック有無 int liSCnt = siSCnt; if (liSCnt < 1) { break; } // スタック数でループ for (j = 0; j < liSCnt; j++) { Stack lzStack; fStackGet(&lzStack); // 各方向へ移動 Pos *lzpPos = &sz2Pos[lzStack.miX][lzStack.miY]; for (k = 0; k < D_WAY_CNT; k++) { if (lzpPos->mc1Con[k] != D_ON) { continue; } // 移動先 int liX = lzStack.miX; int liY = lzStack.miY; switch (k) { case D_WAY_R: liX++; break; case D_WAY_L: liX--; break; case D_WAY_D: liY++; break; case D_WAY_U: liY--; break; } // 到着 if (liX == siW - 1) { if (liY == siH - 1) { return i; } } // スタック - 追加 fStackAdd(liX, liY); } } } return -1; } // 実行メイン int fMain( int piTNo // テスト番号 1~ ) { int i, j; char lc1Buf[1024], lc1Out[1024]; // データ - 初期化 memset(si2Mx, 0, sizeof(si2Mx)); // 横移動 memset(si2My, 0, sizeof(si2My)); // 縦移動 memset(sz2Pos, 0, sizeof(sz2Pos)); // 位置情報 siSCnt = 0; // スタック数 siSSNo = 0; // スタック位置 - セット siSGNo = 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 // 幅・高さ・人数 - 取得 int liHCnt; fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d%d%d", &siW, &siH, &liHCnt); // 人数でループ for (i = 0; i < liHCnt; i++) { // 経路数 - 取得 int liRCnt; fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d", &liRCnt); // 初期位置 int liFrom; fscanf(szpFpI, "%d", &liFrom); // 経路 - 取得 for (j = 0; j < liRCnt; j++) { int liTo; fscanf(szpFpI, "%d", &liTo); // 大小 int liFNo, liTNo; if (liFrom < liTo) { liFNo = liFrom; liTNo = liTo; } else { liFNo = liTo; liTNo = liFrom; } // 商・剰余 int liDF = liFNo / siW; int liDT = liTNo / siW; int liMF = liFNo % siW; int liMT = liTNo % siW; // 移動 - セット if (liDF == liDT) { // 横移動 si2Mx[liDF][liMF]++; si2Mx[liDF][liMT]--; } else { // 縦移動 si2My[liMF][liDF]++; si2My[liMF][liDT]--; } // 位置移動 liFrom = liTo; } fgets(lc1Buf, sizeof(lc1Buf), szpFpI); } // 位置情報 - 接続位置 - セット for (i = 0; i < siH; i++) { int liSum = 0; for (j = 0; j < siW - 1; j++) { liSum += si2Mx[i][j]; if (liSum > 0) { sz2Pos[j][i].mc1Con[D_WAY_R] = D_ON; sz2Pos[j + 1][i].mc1Con[D_WAY_L] = D_ON; } } } for (i = 0; i < siW; i++) { int liSum = 0; for (j = 0; j < siH - 1; j++) { liSum += si2My[i][j]; if (liSum > 0) { sz2Pos[i][j].mc1Con[D_WAY_D] = D_ON; sz2Pos[i][j + 1].mc1Con[D_WAY_U] = D_ON; } } } // 最短距離 - 取得 int liMin = fGetMin(); // 結果 - セット if (liMin < 0) { sprintf(lc1Out, "Odekakedekinai..\n"); } else { sprintf(lc1Out, "%d\n", liMin); } // 結果 - 表示 #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; }