QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#70718 | #5112. Where Am I? | nvmdava | WA | 2ms | 3756kb | C++20 | 1.9kb | 2023-01-07 17:01:51 | 2023-01-07 17:01:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
int n, m;
char c[105][105];
bool is(int x, int y) {
if(x < 1 || x > m || y < 1 || y > n) return 0;
return c[x][y] == 'X';
}
vector<vector<pair<int, int> > > cur, pre;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
pre.push_back(vector<pair<int, int> >());
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
cin>>c[i][j];
pre[0].push_back({i, j});
}
}
ll sum = 0;
int x = 0, y = 0;
int dir = 0, dis = 1, lef = 1;
int i;
for(i = 0; ; i++) {
for(auto& vec : pre) {
vector<pair<int, int> > t0, t1;
for(auto& p : vec) {
if(is(p.ff + x, p.ss + y)) t1.push_back(p);
else t0.push_back(p);
}
if(t0.size() > 1) cur.push_back(t0);
else if(t0.size() == 1) sum += i;
if(t1.size() > 1) cur.push_back(t1);
else if(t1.size() == 1) sum += i;
}
if(cur.empty()) break;
swap(cur, pre);
cur.clear();
x += dx[dir];
y += dy[dir];
if(--lef == 0) {
dis += dir & 1;
lef = dis;
dir = (dir + 1) % 4;
}
}
cout<<setprecision(6)<<sum * 1.0 / n / m<<'\n';
cout<<i<<'\n';
vector<pair<int, int> > all;
for(auto& vec : pre) {
for(auto& p : vec) {
all.push_back(p);
}
}
sort(all.begin(), all.end(), [](const pair<int, int>& lhs, const pair<int, int>& rhs){
return lhs.ff == rhs.ff ? lhs.ff > rhs.ff : lhs.ss < rhs.ss;
});
for(auto& p : all)
cout<<"("<<p.ss<<','<<m + 1 - p.ff<<") ";
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3748kb
input:
1 1 X
output:
0 0 (1,1)
result:
ok correct!
Test #2:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
2 1 .X
output:
0 0 (1,1) (2,1)
result:
ok correct!
Test #3:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
2 1 X.
output:
0 0 (1,1) (2,1)
result:
ok correct!
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 3752kb
input:
1 2 . X
output:
0 0 (1,2) (1,1)
result:
wrong answer Read (1,2) but expected (1,1)