結果
| 問題 |
No.340 雪の足跡
|
| コンテスト | |
| ユーザー |
 Leonardone
|
| 提出日時 | 2016-01-30 08:11:17 |
| 言語 | C90 (gcc 12.3.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,530 bytes |
| コンパイル時間 | 376 ms |
| コンパイル使用メモリ | 28,672 KB |
| 実行使用メモリ | 13,184 KB |
| 最終ジャッジ日時 | 2024-09-21 19:03:22 |
| 合計ジャッジ時間 | 2,212 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 19 RE * 13 |
ソースコード
/* 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; }
}
}
}
{
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..");
}
}