結果
問題 | No.323 yuki国 |
ユーザー |
![]() |
提出日時 | 2019-02-10 18:21:20 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 72 ms / 5,000 ms |
コード長 | 2,370 bytes |
コンパイル時間 | 804 ms |
コンパイル使用メモリ | 31,744 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-06 15:17:38 |
合計ジャッジ時間 | 2,546 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 32 |
ソースコード
#include<stdio.h>#include<stdlib.h>typedef int DequeVal;typedef struct Deque {DequeVal *array;size_t front;size_t last;size_t mask;} Deque;Deque* newDeque(void){const size_t len=2;Deque *d=(Deque *)calloc(len,sizeof(Deque));d->array=(DequeVal *)calloc(len,sizeof(DequeVal));d->front=d->last=0;d->mask=len-1;return d;}void initDeque(Deque *d){d->front=d->last=0;}void freeDeque(Deque *d){free(d->array);free(d);}int isEmpty(Deque *d){return d->front==d->last;}void deque_realloc(Deque *d){DequeVal *array=(DequeVal *)calloc(2*(d->mask+1),sizeof(DequeVal));size_t k=0;for(size_t i=d->front;i!=d->last;i=(i+1)&d->mask) array[k++]=d->array[i];free(d->array);d->array=array;d->front=0;d->last=k;d->mask=2*d->mask+1;}DequeVal pop_front(Deque *d){DequeVal res=d->array[d->front];d->front=(d->front+1)&d->mask;return res;}DequeVal pop_back(Deque *d){d->last=(d->last+d->mask)&d->mask;return d->array[d->last];}DequeVal get_front(Deque *d){return d->array[d->front];}DequeVal get_back(Deque *d){return d->array[(d->last+d->mask)&d->mask];}void push_front(Deque *d,DequeVal v){if(((d->last+1)&d->mask)==d->front){deque_realloc(d);}d->front=(d->front+d->mask)&d->mask;d->array[d->front]=v;}void push_back(Deque *d,DequeVal v){if(((d->last+1)&d->mask)==d->front){deque_realloc(d);}d->array[d->last]=v;d->last=(d->last+1)&d->mask;}#define POS(i,j,k) (((i)*h+(j))*w+(k))void run(void){int h,w;scanf("%d%d",&h,&w);int a,sx,sy;scanf("%d%d%d",&a,&sx,&sy);int b,gx,gy;scanf("%d%d%d",&b,&gx,&gy);char *board=(char *)calloc(h*w+1,sizeof(char));for(int i=0;i<h;i++) scanf("%s",board+i*w);const int m=1111;char *used=(char *)calloc((m+1)*h*w,sizeof(char));Deque *q=newDeque();push_back(q,POS(a,sx,sy));while(!isEmpty(q)){int v=pop_front(q);int s=v/(h*w);int x=v/w%h;int y=v%w;if(s==0 || s==m) continue;int d[]={-1,0,1,0};for(int i=0;i<4;i++){int nx=x+d[i];int ny=y+d[i^1];if(0<=nx && nx<h && 0<=ny && ny<w){int ns=s+(board[nx*w+ny]=='*'?1:-1);if(used[POS(ns,nx,ny)]) continue;used[POS(ns,nx,ny)]=1;push_back(q,POS(ns,nx,ny));}}}puts(used[POS(b,gx,gy)]?"Yes":"No");}int main(void){run();return 0;}