#209819 (C) No.3 ビットすごろく

• 問題: No.3 ビットすごろく
• ユーザー: jokin_tokei
• 提出日時: 2017-10-14 18:16:57
• 言語: C (gcc 12.3.0)
• 結果: RE
• 実行時間: -
• コード長: 2,954 bytes
• コンパイル時間: 174 ms
• コンパイル使用メモリ: 31,232 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-28 19:37:53
• 合計ジャッジ時間: 4,776 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	AC	1 ms; 5,376 KB
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	AC	2 ms; 5,376 KB
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	AC	1 ms; 5,376 KB
testcase_31	RE	-
testcase_32	RE	-

ソースコード

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

// I referred to the follow
// http://www.geocities.jp/m_hiroi/puzzle/puzdoc03.html

#define SUCCESS 1
#define FAILURE 0

#define THOUSAND 1000
#define HUNDRED 100

void bit_map();    // main
int next_go(int num, int goal);  //
int back_go(int num);
int Is_already_reach(int reach_point);

void bit_map() {          // 先に進む中で到着する点までは行くことができる。いったん戻ってから先に進むと到着できる点には行けない。(11のデバッグ途中で力尽きる)
	int goal;
	int queue[HUNDRED][THOUSAND] = { };  // 要素数はfree!!
	int front, rear;
	int back_point, next_point;
	int length[THOUSAND] = { };
	int i;  // loop variable

	scanf("%d", &goal);

	if(goal == 1){
		printf("%d", 1);
		exit(0);
	}

	front = 0;
	rear = 1;
	length[0] = 1;

	queue[0][0] = 1;
	i = 0;

	// infinite loop counter measure
	int debug = 0;
	while (front < rear && debug++ < 100) {
		int len = length[front];  //  ex 1, 12, 123, 124 ...4

		next_point = next_go(queue[front][len - 1], goal);
		if (next_point == goal) {
			printf("%d", len+1);
			exit(0);
		} else if (next_point == FAILURE) {

		} else {    // new root add the queue
			memcpy(queue[rear], queue[front], sizeof(int) * len);
			queue[rear][len] = next_point;
			length[rear] = len + 1;
			rear++;
		}

		// follow is back
		back_point = back_go(queue[front][len-1]);
		if (back_point == FAILURE) {

		} else {   // new back root add the queue
			memcpy(queue[rear], queue[front], sizeof(int) * len);
			queue[rear][len] = back_point;
			length[rear] = len + 1;
			rear++;
		}
		front++;
	}
	printf("-1");

}

int next_go(int num, int goal) {   //Outputs the point that arrived earlier from the given num

	int ad_re_num = 0;
	int next_point = num;

	while (num > 0) {
		ad_re_num += num % 2;
		num = num / 2;
	}

	next_point += ad_re_num;

	if (next_point > goal) {
		return FAILURE;
	}

	if (Is_already_reach(next_point) == SUCCESS) {
		return next_point;
	} else {
		return FAILURE;
	}
}

int back_go(int num) {    //Proceed to the back from the given argument and output the arrival point
	int ad_re_num = 0;
	int back_point = num;

	while (num > 0) {
		ad_re_num += num % 2;
		num = num / 2;
	}

	back_point -= ad_re_num;
	if (back_point < 1) {
		return FAILURE;
	}

	if (Is_already_reach(back_point) == SUCCESS) {
		return back_point;
	} else {
		return FAILURE;
	}
}

int Is_already_reach(int reach_point) {
	static int already_reach[THOUSAND] = { };
	int i = 0;

	already_reach[0] = 1;

	for (i = 0; already_reach[i] != '\0'; i++) {
		if (reach_point == already_reach[i]) {
			return FAILURE;
		}
	}

	already_reach[i] = reach_point;

	return SUCCESS;

}

int main(void) {
//	int ma1[2][5] = {{1,2,3,4,5},{6,7,8,9,0}};
//	int ma2[2][5] = {};
//
//
//	memcpy(ma2[1] , ma1[1], sizeof(int) * 2);

	bit_map();

//	printf("%d  %d",next_go(13,100),back_go(1));

	return 0;
}