結果

問題 No.340 雪の足跡
ユーザー LeonardoneLeonardone
提出日時 2016-01-30 08:12:51
言語 C90
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 6,547 bytes
コンパイル時間 348 ms
コンパイル使用メモリ 28,704 KB
実行使用メモリ 13,056 KB
最終ジャッジ日時 2024-09-21 19:03:25
合計ジャッジ時間 2,087 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 0 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 0 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 0 ms
6,944 KB
testcase_10 AC 0 ms
6,944 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 1 ms
6,948 KB
testcase_14 AC 7 ms
6,944 KB
testcase_15 AC 10 ms
6,940 KB
testcase_16 AC 7 ms
6,940 KB
testcase_17 AC 13 ms
6,944 KB
testcase_18 AC 11 ms
6,944 KB
testcase_19 AC 13 ms
6,940 KB
testcase_20 RE -
testcase_21 RE -
testcase_22 AC 9 ms
13,056 KB
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 AC 16 ms
6,940 KB
testcase_27 AC 3 ms
6,944 KB
testcase_28 AC 16 ms
6,940 KB
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* yukicoder My Practice
 * autoher: Leonarone  NEETSDKASU
 ************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
/************************************************************************/
#define MR__BUFSIZE (1000000)
typedef struct _string { size_t len; char *data; } string;
char mr__buffer[MR__BUFSIZE], *mr__start=mr__buffer; size_t mr__buflen; void solve(void);
int main(void) { mr__buflen = fread(mr__buffer, sizeof(mr__buffer[0]), sizeof(mr__buffer) / sizeof(mr__buffer[0]), stdin);
    if (mr__buflen < MR__BUFSIZE - 1) mr__buffer[mr__buflen] = '\n'; else exit(EXIT_FAILURE); solve(); return 0; }
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MINMAX(v1,v2,a,b) ;(v1)=MIN(a,b);(v2)=MAX(a,b); 
#define DMINMAX(t,v1,v2,a,b) ;t v1=MIN(a,b),v2=MAX(a,b);
#define DIVMOD(v1, v2, a, b) ;(v1)=(a)/(b);(v2)=(a)%(b);
#define DDIVMOD(t, v1, v2, a, b) ;t v1=(a)/(b),v2=(a)%(b);
#define rep(i,s,e) for(i=s;i<e;i++)
#define REP(i,e)   rep(i,0,e)
#define Bv2(a,v1,v2)         ;(v1)=(a)[0];(v2)=(a)[1];
#define Bv3(a,v1,v2,v3)      ;(v3)=(a)[2];Bv2(a,v1,v2);
#define Bv4(a,v1,v2,v3,v4)   ;(v4)=(a)[3];Bv3(a,v1,v2,v3);
#define Dv2(t,a,v1,v2)       ;t v1=(a)[0],v2=(a)[1];
#define Dv3(t,a,v1,v2,v3)    ;t v3=(a)[2];Dv2(t,a,v1,v2);
#define Dv4(t,a,v1,v2,v3,v4) ;t v4=(a)[3];Dv3(t,a,v1,v2,v3);
#define V_ALLOCSIZE (20)
typedef struct _vector { size_t size; size_t capa; char data[0]; } VectorT, *Vector, **PPVector;
Vector newVec(size_t n, size_t b) { size_t a=MAX(V_ALLOCSIZE,n);Vector r=(Vector)calloc(1,a*b+sizeof(VectorT)); r->size=n; r->capa=a; return r; }
void extendVec(PPVector p, size_t b) { Vector v=*p;if(v->size==v->capa){v->capa+=V_ALLOCSIZE; v=*p=(Vector)realloc(*p,v->capa*b+sizeof(VectorT));}}
#define CUP(a, b) a##b
#define CUP3(a, b, c) a##b##c
#define VEC_DEF(_T,_I) \
    typedef struct CUP3(_,_I,vector) { size_t size; size_t capa; _T value[0]; } CUP(_I,VectorT),*CUP(_I,Vector),**CUP3(PP,_I,Vector); \
    CUP(_I,Vector) CUP3(new,_I,V)(size_t n) { return (CUP(_I,Vector))newVec(n,sizeof(_T)); } \
    CUP(_I,Vector) CUP3(alloc,_I,V)(size_t n) { CUP(_I,Vector) r = (CUP(_I,Vector))newVec(n,sizeof(_T)); r->size = 0; return r; } \
    CUP(_I,Vector) CUP3(add,_I,V)(CUP3(PP,_I,Vector) p, _T x) { extendVec((PPVector)p, sizeof(_T)); (*p)->value[(*p)->size++]=x; return *p; }
VEC_DEF(int,I); VEC_DEF(string,S); VEC_DEF(IVector,IV); VEC_DEF(SVector,SV); VEC_DEF(char,C);
#define V(v,i) ((v)->value[(i)])
#define VV(v,y,x) V(V(v,y),x)
#define PrintV(v,f,d) {int PV_i;for(PV_i=0;PV_i<(v)->size;PV_i++)printf(f d,V((v),PV_i));putchar('\n');}
SVector strsplit(string str, char d) {SVector vec=newSV(0);char *e=str.data,*s;string t;
    for(;;){s=e;while(*e&&*e!=d)e++;if(e==str.data)return vec;t.data=s;t.len=e-s;addSV(&vec,t);if(*e==0)break;*e++=0;}return vec;}
string strjoin(SVector v,char d){string t,r={0};int i;for(i=0;i<v->size;i++)r.len+=v->value[i].len;if(d)r.len+=v->size-1;
    {char *p=r.data=(char*)malloc(sizeof(char)*(r.len+1));for(i=0;i<v->size;i++)
    {if(i&&d)*p++=d;t=v->value[i];memcpy(p,t.data,t.len*sizeof(char));p+=t.len;}r.data[r.len]=0;}return r;}
int     isEOF(void) { return *mr__start == '\0'; }
void    nextLine(void) { while (*mr__start != '\n') mr__start++; *mr__start++ = '\0'; }
int     ti(string s) { int i,r=0,m=*s.data=='-'; for(i=m;i<(int)s.len;i++)r=r*10+(int)(s.data[i]-'0'); return m ? -r : r; }
string  gs(void) { string r = {0, mr__start}; nextLine(); r.len = mr__start - r.data - 1; return r; }
int     gi(void) { return ti(gs()); }
SVector gss(void) { return strsplit(gs(), ' '); }
IVector gis(void) { SVector v=gss();IVector r=newIV(v->size);int i;for(i=0;i<v->size;i++)r->value[i]=ti(v->value[i]);free(v);return r;}
SVector ngs(int n) { SVector r=newSV(n); int i; for(i=0;i<n;i++)r->value[i]=gs(); return r; }
IVector ngi(int n) { IVector r=newIV(n); int i; for(i=0;i<n;i++)r->value[i]=gi(); return r; }
SVVector ngss(int n) { SVVector r=newSVV(n); int i; for(i=0;i<n;i++)r->value[i]=gss(); return r; }
IVVector ngis(int n) { IVVector r=newIVV(n); int i; for(i=0;i<n;i++)r->value[i]=gis(); return r; }
int iAsc(const void *a, const void *b) { return *(int*)a - *(int*)b; }
int iDec(const void *a, const void *b) { return *(int*)b - *(int*)a; }
/************************************************************************/


void solve(void) {
    IVector a = gis();
    Dv3(int, a->value, w, h, n);
    IVVector hr = newIVV(h), vr = newIVV(h), f = newIVV(h);
    int i;
    
    REP(i,h) {
        V(hr,i) = newIV(w);
        V(vr,i) = newIV(w);
        V(f,i) = newIV(w);
    }
    
    REP(i,n) {
        int m = gi();
        IVector b = gis();
        int j,k;
        REP(j,m) {
            DMINMAX(int,b2,b1,V(b,j), V(b,j+1));
            DDIVMOD(int,b1y,b1x,b1,w);
            DDIVMOD(int,b2y,b2x,b2,w);
            if (b1y == b2y) {
                for (k = b2x; k < b1x; k++) { VV(hr,b1y,k) = 1; }
            } else {
                for (k = b2y; k < b1y; k++) { VV(vr,k,b1x) = 1; }
            }
        }
        free(b);
    }
    {
        int g = ((h - 1) << 10) | (w - 1);
        IVector cu = allocIV(h*w), nx = allocIV(h*w);
        addIV(&cu, 0);
        VV(f,0,0) = 1;
        for (i = 0; i < h * w; i++) {
            int j;
            nx->size = 0;
            for (j = 0; j < cu->size; j++) {
                int v = V(cu,j);
                if (v == g) {
                    printf("%d\n", i);
                    return;
                }
                int y = v >> 10;
                int x = v & 1023;
                if (x > 0 && !VV(f,y,x-1) && VV(hr,y,x-1)) {
                    VV(f,y,x-1) = 1;
                    addIV(&nx, (y << 10) | (x-1));
                }
                if (x < w - 1 && !VV(f,y,x+1) && VV(hr,y,x)) {
                    VV(f,y,x+1) = 1;
                    addIV(&nx, (y << 10) | (x+1));
                }
                if (y > 0 && !VV(f,y-1,x) && VV(vr,y-1,x)) {
                    VV(f,y-1,x) = 1;
                    addIV(&nx, ((y-1) << 10) | x);
                }
                if (y < h - 1 && !VV(f,y+1,x) && VV(vr,y,x)) {
                    VV(f,y+1,x) = 1;
                    addIV(&nx, ((y+1) << 10) | x);
                }
            }
            {
                IVector t = cu;
                cu = nx;
                nx = t;
            }
            if (cu->size == 0) {
                break;
            }
        }
        puts("Odekakedekinai..");
    }
    
}
0