結果
| 問題 |
No.340 雪の足跡
|
| コンテスト | |
| ユーザー |
 kapo
|
| 提出日時 | 2016-05-11 17:35:25 |
| 言語 | C90 (gcc 12.3.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 14 WA * 1 TLE * 1 -- * 16 |
コンパイルメッセージ
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]);
| ^~~~~~~~~~~~~~~~~~
ソースコード
#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;
}