QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#100786 | #4426. Divided Mechanism | Yanagi_Origami# | AC ✓ | 95ms | 3460kb | C++20 | 2.3kb | 2023-04-28 08:04:44 | 2023-04-28 08:04:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define forn(i,a,b) for(int i=(a); (i)<(b); i++)
#define fore(i,a,b) for(int i=(a); (i)<=(b); i++)
#define pb push_back
#define sz(a) static_cast<int>((a).size())
#define F first
#define S second
constexpr int INF = 1'000'000'000;
using ll = long long;
constexpr int C = 4;
unordered_map<char, array<int, 2>> dir = {
{'N', {-1, 0}}, {'S', {1, 0}}, {'E', {0, 1}}, {'W', {0, -1}}
};
bool oob(int n, int m, int x, int y)
{
return min(x,y)<0 || x>=n || y>=m;
}
void solve()
{
int n,m,Q; cin>>n>>m>>Q;
int n2 = C * n, m2 = C * m;
vector<string> s(n2, string(m2, '.'));
vector<string> s1(n2, string(m2, '.'));
forn(i,0,n) forn(j,0,m)
{
cin>>s[i+n+n/2][j+m+m/2];
}
string upd; cin>>upd;
forn(z,0,Q)
{
// cout<<"z="<<z<<endl;
char c = upd[z];
array<int, 2> d = dir[c];
int min_dist=INF;
forn(i,0,n2) forn(j,0,m2)
{
if(s[i][j] != 'B') continue;
int x=i+d[0], y=j+d[1];
while(!oob(n2, m2, x, y))
{
if (s[x][y] != '.') break;
x += d[0];
y += d[1];
}
if (oob(n2, m2, x, y) || s[x][y] == 'B') continue;
min_dist = min(min_dist, abs(x - i) + abs(y - j) - 1);
}
// cout<<"z="<<z<<" min_dist="<<min_dist<<'\n';
if (min_dist == INF)
{
cout<<"TAK\n";
return;
}
// update map
forn(i,0,n2) forn(j,0,m2)
{
// cout<<">>> 1: "<<i<<" "<<j<<endl;
if (s[i][j] != 'B') s1[i][j] = s[i][j];
else s1[i][j] = '.';
}
forn(i,0,n2) forn(j,0,m2)
{
// cout<<">>> 2: "<<i<<" "<<j<<endl;
if (s[i][j] != 'B') continue;
int x = i + min_dist * d[0];
int y = j + min_dist * d[1];
s1[x][y] = 'B';
}
forn(i,0,n2) forn(j,0,m2) s[i][j] = s1[i][j];
// forn(i,0,n2) cout<<s[i]<<'\n';
// cout<<'\n';
}
cout<<"NIE\n";
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int t; cin>>t;
forn(i,0,t) solve();
}
详细
Test #1:
score: 100
Accepted
time: 95ms
memory: 3460kb
input:
1000 10 9 4 AA...AAAA A......AA A..BBB..A A...B...A A...B...A AA..BBAAA A..BB...A A......AA A...AAAAA AAAAAAAAA WSEN 9 10 4 AAAAAAAAAA A...A....A A......... A..B...B.. AA.BBBBB.. AA..B..B.A AA..A....A AAA.A...AA AAAAAAAAAA ESNE 9 10 7 AAAAAAAAAA A...A....A A......... A..B...B.. AA.BBBBB.. AA..B..B.A...
output:
TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK ...
result:
ok 1000 lines
Extra Test:
score: 0
Extra Test Passed