#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int A[100005];
int B[200005];
int res[805][805];
bool vis[805][805];
int T[805][805];
int N, R, C;
int val[16];
bool in(int x, int y) {
return 0<=x&&x<R&&0<=y&&y<C;
}
int D[805][805];
typedef pair<int,int> P;
bool pos[805][805][4];
int dir_map[3][3] = {
{ -1,3,-1 },
{ 2,-1,0 },
{ -1,1,-1 }
};
int all_cnt = 0;
int num(int x, int y) {
return C*x+y;
}
set<P> S;
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> R >> C;
string s;
cin >> s;
int i, j;
for(i=0;i<N;i++) {
for(j=0;j<4;j++) {
if(s[i]=="WNES"[j]) A[i] = j;
}
}
for(j=0;j<16;j++) {
for(i=0;i<N;i++) B[i] = 0;
bool VS[4] = {0, 0, 0, 0};
for(int k = 0; k < 4; k++) {
if(j&(1<<k)) VS[k] = true;
}
for(i=0;i<N;i++) {
if(VS[A[i]]) B[i] = 1;
}
for(i=N;i<2*N;i++) B[i] = B[i-N];
for(i=1;i<2*N;i++) {
if(B[i]!=0) B[i] = B[i-1] + 1;
}
for(i=0;i<2*N;i++) val[j] = max(val[j], B[i]);
if(val[j] >= N) val[j] = 100001;
}
for(i=0;i<R;i++) {
for(j=0;j<C;j++) cin >> D[i][j];
}
for(i=0;i<R;i++) {
for(j=0;j<C;j++) {
T[i][j] = 0;
}
}
for(i=0;i<R;i++) {
for(j=0;j<C;j++) {
if(D[i][j]==0) continue;
//cout << i << ' ' << j << "'s Turn\n";
vis[i][j] = true;
res[i][j] = 1;
queue<P> Q;
vector<array<int, 2>> F;
F.push_back({i, j});
for(int dir = 0; dir < 4; dir++) {
int x1 = i + dx[dir], y1 = j + dy[dir];
if(in(x1, y1)) {
if(T[x1][y1]==0) F.push_back({x1, y1});
T[x1][y1] += (1<<dir);
if(D[x1][y1]!=0&&val[T[x1][y1]]>=D[x1][y1]) Q.push(P(x1, y1));
}
}
while(!Q.empty()) {
P k = Q.front();
Q.pop();
int x = k.first, y = k.second;
//cout << x << ' ' << y <<'\n';
all_cnt++;
if(vis[x][y]) continue;
vis[x][y] = true;
S.insert(P(num(i, j), num(x, y)));
if(S.find(P(num(x, y), num(i, j)))!=S.end()) {
res[i][j] = res[x][y];
break;
}
res[i][j]++;
for(int k2 = 0; k2 < 4; k2++) {
int x1 = x + dx[k2], y1 = y + dy[k2];
if(in(x1, y1)) {
if(vis[x1][y1]) continue;
if(val[T[x1][y1]]>=D[x1][y1]) continue;
if(T[x1][y1]==0) F.push_back({x1, y1});
T[x1][y1] += (1<<k2);
if(D[x1][y1]!=0&&val[T[x1][y1]]>=D[x1][y1]) Q.push(P(x1, y1));
}
}
}
for(auto k : F) T[k[0]][k[1]] = 0;
for(auto k : F) vis[k[0]][k[1]] = false;
}
}
int mi = R*C+1, micnt = 0;
for(i=0;i<R;i++) {
for(j=0;j<C;j++) {
if(D[i][j]==0) continue;
if(res[i][j] < mi) {
mi = res[i][j];
micnt = 0;
}
if(res[i][j]==mi) micnt++;
}
}
/*for(i=0;i<R;i++) {
for(j=0;j<C;j++) cout << res[i][j] << ' ';
cout << '\n';
}*/
cout << mi << '\n' << micnt;
//cout <<'\n' << all_cnt;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
