QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#883738 | #10002. Catch The Flea | bulijiojiodibuliduo# | AC ✓ | 0ms | 5980kb | C++17 | 1.8kb | 2025-02-05 18:33:58 | 2025-02-05 18:33:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=2010;
int n,m,k;
queue<PII> q;
char s[N][N];
int vis[N][N];
set<PII> l,r,u,d;
int main() {
scanf("%d%d%d",&n,&m,&k);
rep(i,0,n) scanf("%s",s[i]);
rep(i,0,n) rep(j,0,m) {
vis[i][j]=0;
if (s[i][j]=='L'&&j-k<0) vis[i][j]=1;
if (s[i][j]=='R'&&j+k>=m) vis[i][j]=1;
if (s[i][j]=='U'&&i-k<0) vis[i][j]=1;
if (s[i][j]=='D'&&i+k>=n) vis[i][j]=1;
if (vis[i][j]) q.push(mp(i,j));
else {
if (s[i][j]=='L') l.insert(mp(i,j));
if (s[i][j]=='R') r.insert(mp(i,j));
if (s[i][j]=='U') u.insert(mp(j,i));
if (s[i][j]=='D') d.insert(mp(j,i));
}
}
while (!q.empty()) {
auto [x,y]=q.front(); q.pop();
auto add=[&](set<PII> &s,int x,int y1,int y2,int fl=0) {
while (1) {
auto it=s.lower_bound(mp(x,y1));
if (it!=s.end()&&it->fi==x&&it->se<=y2) {
auto [a,b]=*it;
if (fl) swap(a,b);
vis[a][b]=1;
q.push(mp(a,b));
s.erase(it);
} else {
break;
}
}
};
add(r,x,y-k,y);
add(l,x,y,y+k);
add(d,y,x-k,x,1);
add(u,y,x,x+k,1);
}
int ans=0;
rep(i,0,n) rep(j,0,m) if (vis[i][j]) ans+=1;
printf("%d\n",ans);
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5980kb
input:
5 5 2 DDDRD DDDDD RDLUL UURUU UUUUU
output:
14
result:
ok answer is '14'