QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#68833 | #5112. Where Am I? | chenshi# | TL | 0ms | 0kb | C++14 | 1.7kb | 2022-12-21 10:41:03 | 2022-12-21 10:41:05 |
Judging History
answer
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int o=1e6;
int n,m,dx[o],dy[o],cnt,ans1,ans2;char s[110][110];
struct State{int sx,sy,x,y;};
vector<State> bg1,bg2,Ans;
void slv(vector<State> vec,int t){
if(t>=cnt) while(1);
if((int)vec.size()==1){
ans1+=--t;
if(t>ans2) ans2=t,Ans.clear();
if(t==ans2) Ans.push_back(vec[0]);
return;
}
for(int c1,c2;1;++t){
c1=c2=0;
for(int i=vec.size();i--;){
vec[i].x+=dx[t];vec[i].y+=dy[t];
if(vec[i].x>=1&&vec[i].x<=n&&vec[i].y>=1&&vec[i].y<=m&&s[vec[i].x][vec[i].y]=='X') ++c1;
else ++c2;
}
if(c1&&c2){
vector<State> v1,v2;
v1.reserve(c1);v2.reserve(c2);
for(int i=vec.size();i--;)
if(vec[i].x>=1&&vec[i].x<=n&&vec[i].y>=1&&vec[i].y<=m&&s[vec[i].x][vec[i].y]=='X') v1.push_back(vec[i]);
else v2.push_back(vec[i]);
vec.clear();slv(v1,t+1);slv(v2,t+1);
break;
}
}
}
inline bool cmp(State A,State B){if(A.sy^B.sy) return A.sy<B.sy;return A.sx<B.sx;}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<500;++i){
for(int j=1;j<2*i;++j) dx[++cnt]=0,dy[cnt]=1;
for(int j=1;j<2*i;++j) dx[++cnt]=1,dy[cnt]=0;
for(int j=1;j<=2*i;++j) dx[++cnt]=0,dy[cnt]=-1;
for(int j=1;j<=2*i;++j) dx[++cnt]=-1,dy[cnt]=0;
}
for(int j=1;j<=m;++j) for(int i=1;i<=n;++i)
do s[i][m-j+1]=getchar();while(s[i][m-j+1]-'X'&&s[i][m-j+1]-'.');
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
if(s[i][j]=='X') bg1.push_back((State){i,j,i,j});
else bg2.push_back((State){i,j,i,j});
slv(bg1,1);slv(bg2,1);
printf("%.5lf\n%d\n",ans1*1.0/(n*m),ans2);
sort(Ans.begin(),Ans.end(),cmp);
for(int i=0,sz=Ans.size();i<sz;++i) printf("(%d,%d) ",Ans[i].sx,Ans[i].sy);
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
1 1 X