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