QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#884195 | #10002. Catch The Flea | Kevin5307 | AC ✓ | 0ms | 3968kb | C++23 | 2.4kb | 2025-02-05 22:02:08 | 2025-02-05 22:02:11 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
string dir="UDLR";
int n,m,k;
set<int> st[2020][4];
int ok[2020][2020];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
for(int j=1;j<=m;j++)
{
char ch=s[j-1];
for(int d=0;d<4;d++)
if(dir[d]==ch)
st[(d<2)?(j):(i)][d].insert((d<2)?(i):(j));
}
}
queue<int> q;
for(int i=0;i<=n+1;i++)
for(int j=0;j<=m+1;j++)
if(!i||!j||i==n+1||j==m+1)
{
ok[i][j]=1;
q.push(i);
q.push(j);
}
while(!q.empty())
{
int x=q.front();
q.pop();
int y=q.front();
q.pop();
{
auto it=st[y][0].lower_bound(x);
while(it!=st[y][0].end()&&*it<=x+k)
{
ok[*it][y]=1;
q.push(*it);
q.push(y);
it++;
st[y][0].erase(prev(it));
}
}
{
auto it=st[y][1].lower_bound(x);
if(it!=st[y][1].begin())
{
it--;
while(*it>=x-k)
{
ok[*it][y]=1;
q.push(*it);
q.push(y);
if(it==st[y][1].begin())
{
st[y][1].erase(it);
break;
}
it--;
st[y][1].erase(next(it));
}
}
}
{
auto it=st[x][2].lower_bound(y);
while(it!=st[x][2].end()&&*it<=y+k)
{
ok[x][*it]=1;
q.push(x);
q.push(*it);
it++;
st[x][2].erase(prev(it));
}
}
{
auto it=st[x][3].lower_bound(y);
if(it!=st[x][3].begin())
{
it--;
while(*it>=y-k)
{
ok[x][*it]=1;
q.push(x);
q.push(*it);
if(it==st[x][3].begin())
{
st[x][3].erase(it);
break;
}
it--;
st[x][3].erase(next(it));
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans+=ok[i][j];
cout<<ans<<'\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3968kb
input:
5 5 2 DDDRD DDDDD RDLUL UURUU UUUUU
output:
14
result:
ok answer is '14'