Submission #14538

#TimeUsernameProblemLanguageResultExecution timeMemory
14538jackae98물병 (JOI14_bottle)C++98
0 / 100
5000 ms1968 KiB
#include <stdio.h> #include <queue> #include <stdlib.h> int h,w,p,q; struct Coor2{ int x,y; int dis; }; struct Coor{ int x,y; }b[210]; char a[210][210]; int dis[210][210]; int visit[210][210]; int dx[4] = {0,-1,0,1}; int dy[4] = {-1,0,1,0}; std::queue<Coor2> Q; int max(int a,int b) { return a>b?a:b; } void g(){ for(int k=1;k<=p;k++){ for(int i=1;i<=p;i++){ for(int j=1;j<=p;j++){ if(max(dis[i][k],dis[k][j]) < dis[i][j]){ dis[i][j] = max(dis[i][k],dis[k][j]); } } } } } int getDis(int st,int ed){ while(!Q.empty()){ Q.pop(); } int ex = b[ed].x; int ey = b[ed].y; Coor2 init; init.x = b[st].x; init.y = b[st].y; init.dis = 0; Q.push(init); while(!Q.empty()){ Coor2 cur = Q.front(); Q.pop(); if(cur.x==ex&&cur.y==ey){ return cur.dis; } for(int i=0;i<4;i++){ if(cur.x+dx[i]>=0 && cur.x+dx[i]<h && cur.y+dy[i]>=0 && cur.y+dy[i]<w && a[cur.x+dx[i]][cur.y+dy[i]] == '.'&&visit[cur.x+dx[i]][cur.y+dy[i]] != st*(2*p)+ed){ Coor2 next; next.x = cur.x+dx[i]; next.y = cur.y+dy[i]; visit[next.x][next.y] = st*(2*p)+ed; if(next.x==ex&&next.y==ey){ return cur.dis; } next.dis = cur.dis+1; Q.push(next); } } } return 987654321; } void preinit(){ for(int i=1;i<=p;i++){ for(int j=1;j<=p;j++){ dis[i][j] = getDis(i,j); } } } int dijkstra(int st,int ed){ } int main() { scanf("%d %d %d %d",&h,&w,&p,&q); if(p>=210){ printf("Cutting"); return 0; } for(int i=0;i<h;i++){ scanf("%s",a[i]); } for(int i=1;i<=p;i++){ int x,y; scanf("%d %d",&x,&y); b[i].x = x-1; b[i].y = y-1; } preinit(); /*if(q==1){ int s,t; scanf("%d %d",&s,&t); printf("%d",dijkstra(s,t)); }*/ //else{ g(); for(int i=1;i<=q;i++){ int s,t; scanf("%d %d",&s,&t); if(dis[s][t]==987654321) printf("-1"); else printf("%d",dis[s][t]); } //} }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...