QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#883738#10002. Catch The Fleabulijiojiodibuliduo#AC ✓0ms5980kbC++171.8kb2025-02-05 18:33:582025-02-05 18:33:59

Judging History

This is the latest submission verdict.

  • [2025-02-05 18:33:59]
  • Judged
  • Verdict: AC
  • Time: 0ms
  • Memory: 5980kb
  • [2025-02-05 18:33:58]
  • Submitted

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'