結果

問題 No.340 雪の足跡
ユーザー kapokapo
提出日時 2016-05-11 19:30:17
言語 C90
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 5,442 bytes
コンパイル時間 306 ms
コンパイル使用メモリ 25,088 KB
実行使用メモリ 62,544 KB
最終ジャッジ日時 2024-10-05 13:46:45
合計ジャッジ時間 4,626 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 52 ms
62,544 KB
testcase_01 AC 51 ms
55,644 KB
testcase_02 AC 10 ms
16,512 KB
testcase_03 AC 55 ms
55,592 KB
testcase_04 AC 11 ms
16,384 KB
testcase_05 WA -
testcase_06 AC 57 ms
55,756 KB
testcase_07 AC 11 ms
16,512 KB
testcase_08 AC 11 ms
16,384 KB
testcase_09 AC 55 ms
55,652 KB
testcase_10 AC 55 ms
55,500 KB
testcase_11 AC 57 ms
55,696 KB
testcase_12 AC 53 ms
55,624 KB
testcase_13 AC 55 ms
55,636 KB
testcase_14 AC 66 ms
55,736 KB
testcase_15 AC 72 ms
55,624 KB
testcase_16 AC 66 ms
55,772 KB
testcase_17 AC 78 ms
55,812 KB
testcase_18 AC 72 ms
55,724 KB
testcase_19 AC 78 ms
55,772 KB
testcase_20 TLE -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:15:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |         scanf("%d %d %d", &w, &h, &n);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:17:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   17 |                 scanf("%d", &m);
      |                 ^~~~~~~~~~~~~~~
main.c:19:25: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   19 |                         scanf("%d", &b[j]);
      |                         ^~~~~~~~~~~~~~~~~~

ソースコード

diff # 

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

int main(void)
{
	int i, j, k, n, m, h, w, **t, b[1000], p1[2], p2[2], cnt=0;
	int bit_n = 0x0008;
	int bit_e = 0x0004;
	int bit_w = 0x0002;
	int bit_s = 0x0001;
	if( (t = (int **)calloc(1000, sizeof(int *))) == NULL) return 0;
	for( i = 0; i < 1000; i++) {
		if( (t[i] = (int *)calloc(2000, sizeof(int *))) == NULL) return 0;
	}
	scanf("%d %d %d", &w, &h, &n);
	for( i = 0; i < n; i++) {
		scanf("%d", &m);
		for( j = 0; j <= m; j++) {
			scanf("%d", &b[j]);
		}

		for( j = 0; j < m; j++) {
			p1[0] = b[j]/w;		p1[1] = b[j]%w;		//(y1,x1)
			p2[0] = b[j+1]/w;	p2[1] = b[j+1]%w;	//(y2,x2)
			if( p1[0] == p2[0] ) {
				if( p1[1] > p2[1] ) {			//E to W
					for( k = 0; p2[1] < p1[1]-k; k++) {
						t[ p1[0] ][ (p1[1]-k)*2   ] |= bit_w;
						t[ p2[0] ][ (p1[1]-1-k)*2 ] |= bit_e;
					}
				} else if( p2[1] > p1[1] ) {		//W to E
					for( k = 0; p1[1]+k < p2[1]; k++) {
						t[ p1[0] ][ (p1[1]+k)*2   ] |= bit_e;
						t[ p2[0] ][ (p1[1]+1+k)*2 ] |= bit_w;
					}
				}
			} else if ( p1[1] == p2[1] ) {
				if( p1[0] > p2[0] ) {			//N to S
					for( k = 0; p2[0] < p1[0]-k; k++) {
						t[ p1[0]-k   ][ (p1[1])*2 ] |= bit_s;
						t[ p1[0]-1-k ][ (p2[1])*2 ] |= bit_n;
					}
				} else if( p2[0] > p1[0] ) {		//S to N
					for( k = 0; p1[0]+k < p2[0]; k++) {
						t[ p1[0]+k   ][ (p1[1])*2 ] |= bit_n;
						t[ p1[0]+1+k ][ (p2[1])*2 ] |= bit_s;
					}
				}

			}
		}
	}
	if( !t[0][0] || !t[h-1][(w-1)*2]) {
		printf("Odekakedekinai..\n");
		return 0;
	} else if( t[0][0] == 1 || t[h-1][(w-1)*2] == 1) {
		printf("0\n");
		return 0;
	}

	typedef struct {
		int front, rear, count, size, **buf;
	}Queue;

	Queue *que;
	if( (que = (Queue *)malloc(sizeof(Queue))) == NULL) return 0;
	if( (que->buf = (int **)malloc(sizeof(int *) * 1000000)) == NULL) return 0;
	for( i = 0; i < 1000000; i++) {
		if( (que->buf[i] = (int *)malloc(sizeof(int) * 2)) == NULL) return 0;
	}
	que->front = 0;
	que->rear = 0;
	que->count = 0;
	que->size = 1000000;
	que->buf[ que->front ][0] = 0;	//y
	que->buf[ que->front ][1] = 0;	//x
	que->rear++;

	while( que->front != que->rear ) {	
		if( t[ que->buf[ que->front ][0] ][ que->buf[ que->front ][1]*2 ] & bit_n ) { //現在地がNと繋がっている時
			if( !t[ que->buf[ que->front ][0]+1 ][ que->buf[ que->front ][1]*2+1 ]	//NのNODEが0か
			|| ( t[ que->buf[ que->front ][0]+1 ][ que->buf[ que->front ][1]*2+1 ]	//NのNODEより現在地のNODE+1の方が小さい時　
			&& ( t[ que->buf[ que->front ][0]+1 ][ que->buf[ que->front ][1]*2+1 ] > ( t[ que->buf[ que->front ][0] ][ que->buf[ que->front ][1]*2+1 ]+1)) ) ) {
				t[ que->buf[ que->front ][0]+1 ][ que->buf[ que->front ][1]*2+1 ] = t[ que->buf[ que->front ][0] ][ que->buf[ que->front ][1]*2+1 ]+1;	//NODEを更新
				que->buf[ que->rear ][0] = que->buf[ que->front ][0]+1;	//キューに追加
				que->buf[ que->rear ][1] = que->buf[ que->front ][1];
				que->rear++;
				if( que->rear == que->size ) que->rear = 0;
			}
		}
		if( t[ que->buf[ que->front ][0] ][ que->buf[ que->front ][1]*2 ] & bit_e ) { //現在地がEと繋がっている時
			if( !t[ que->buf[ que->front ][0] ][ (que->buf[ que->front ][1]+1)*2+1 ]	
			|| ( t[ que->buf[ que->front ][0] ][ (que->buf[ que->front ][1]+1)*2+1 ]	
			&& ( t[ que->buf[ que->front ][0] ][ (que->buf[ que->front ][1]+1)*2+1 ] > ( t[ que->buf[ que->front ][0] ][ que->buf[ que->front ][1]*2+1 ]+1)) ) ) {
				t[ que->buf[ que->front ][0] ][ (que->buf[ que->front ][1]+1)*2+1 ] = t[ que->buf[ que->front ][0] ][ que->buf[ que->front ][1]*2+1 ]+1;
				que->buf[ que->rear ][0] = que->buf[ que->front ][0];	
				que->buf[ que->rear ][1] = que->buf[ que->front ][1]+1;
				que->rear++;
				if( que->rear == que->size ) que->rear = 0;
			}
		}
		if( t[ que->buf[ que->front ][0] ][ que->buf[ que->front ][1]*2 ] & bit_s ) { //現在地がSと繋がっている時
			if( !t[ que->buf[ que->front ][0]-1 ][ que->buf[ que->front ][1]*2+1 ]	
			|| ( t[ que->buf[ que->front ][0]-1 ][ que->buf[ que->front ][1]*2+1 ]	
			&& ( t[ que->buf[ que->front ][0]-1 ][ que->buf[ que->front ][1]*2+1 ] > ( t[ que->buf[ que->front ][0] ][ que->buf[ que->front ][1]*2+1 ]+1)) ) ) {
				t[ que->buf[ que->front ][0]-1 ][ que->buf[ que->front ][1]*2+1 ] = t[ que->buf[ que->front ][0] ][ que->buf[ que->front ][1]*2+1 ]+1;
				que->buf[ que->rear ][0] = que->buf[ que->front ][0]-1;	
				que->buf[ que->rear ][1] = que->buf[ que->front ][1];
				que->rear++;
				if( que->rear == que->size ) que->rear = 0;
			}
		}
		if( t[ que->buf[ que->front ][0] ][ que->buf[ que->front ][1]*2 ] & bit_w ) { //現在地がWと繋がっている時
			if( !t[ que->buf[ que->front ][0] ][ (que->buf[ que->front ][1]-1)*2+1 ]	
			|| ( t[ que->buf[ que->front ][0] ][ (que->buf[ que->front ][1]-1)*2+1 ]	
			&& ( t[ que->buf[ que->front ][0] ][ (que->buf[ que->front ][1]-1)*2+1 ] > ( t[ que->buf[ que->front ][0] ][ que->buf[ que->front ][1]*2+1 ]+1)) ) ) {
				t[ que->buf[ que->front ][0] ][ (que->buf[ que->front ][1]-1)*2+1 ] = t[ que->buf[ que->front ][0] ][ que->buf[ que->front ][1]*2+1 ]+1;
				que->buf[ que->rear ][0] = que->buf[ que->front ][0];	
				que->buf[ que->rear ][1] = que->buf[ que->front ][1]-1;
				que->rear++;
				if( que->rear == que->size ) que->rear = 0;
			}
		}
		que->front++;
		if( que->front == que->size ) que->front = 0;
	}

	if(  t[h-1][(w-1)*2+1] ) {
		printf("%d\n", t[h-1][(w-1)*2+1]);
	} else {
		printf("Odekakedekinai..\n");
	}

	return 0;
}
0