#91151 (C90) No.340 雪の足跡

提出ソース

結果

問題	No.340 雪の足跡
ユーザー	kapo
提出日時	2016-05-11 17:35:25
言語	C90 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	5,358 bytes
コンパイル時間	225 ms
コンパイル使用メモリ	24,960 KB
実行使用メモリ	27,428 KB
最終ジャッジ日時	2024-10-05 13:44:30
合計ジャッジ時間	5,556 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	15 ms 27,428 KB
testcase_01	AC	15 ms 20,608 KB
testcase_02	AC	10 ms 16,640 KB
testcase_03	AC	14 ms 20,480 KB
testcase_04	AC	10 ms 16,512 KB
testcase_05	WA	-
testcase_06	AC	14 ms 20,480 KB
testcase_07	AC	11 ms 16,512 KB
testcase_08	AC	10 ms 16,512 KB
testcase_09	AC	14 ms 20,480 KB
testcase_10	AC	15 ms 20,352 KB
testcase_11	AC	16 ms 20,608 KB
testcase_12	AC	18 ms 20,480 KB
testcase_13	AC	16 ms 20,480 KB
testcase_14	AC	26 ms 20,480 KB
testcase_15	AC	30 ms 20,480 KB
testcase_16	AC	24 ms 20,480 KB
testcase_17	AC	36 ms 20,608 KB
testcase_18	AC	31 ms 20,480 KB
testcase_19	AC	37 ms 20,608 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]);
      |                         ^~~~~~~~~~~~~~~~~~

ソースコード

raw source code

#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;
	}

	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 *) * 100000)) == NULL) return 0;
	for( i = 0; i < 100000; i++) {
		if( (que->buf[i] = (int *)malloc(sizeof(int) * 2)) == NULL) return 0;
	}
	que->front = 0;
	que->rear = 0;
	que->count = 0;
	que->size = 100000;
	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;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード