#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
const int N = 100 + 10;
int n,m,k;
string s;
char a[N][N];
int seen[N][N][N];
int cur = 0;
int x[1000];
int y[1000];
queue<pair<pair<int,int>,int>> Q;
void deal(int i,int j,int ind,char d){
i += x[d];
j += y[d];
if (i > n or j > m or i < 1 or j < 1)
return;
if (seen[i][j][ind+1] != cur)
Q.push({{i,j},ind+1});
seen[i][j][ind+1] = cur;
}
void bfs(int sr,int sc){
cur++;
Q.push({{sr,sc},0});
seen[sr][sc][0] = cur;
// cout<<sr<<" "<<sc<<endl;
while (!Q.empty()){
auto [a1,ind] = Q.front();
Q.pop();
auto [i,j] = a1;
// cout<<i<<" "<<j<<" "<<ind<<endl;
if (a[i][j] == '#')
continue;
if (ind == k){
seen[0][i][j] = true;
continue;
}
if (s[ind] != '?')
deal(i,j,ind,s[ind]);
else{
deal(i,j,ind,'N');
deal(i,j,ind,'E');
deal(i,j,ind,'S');
deal(i,j,ind,'W');
}
}
}
signed main(){
x['N'] = y['W'] = -1;
x['S'] = y['E'] = 1;
cin>>n>>m>>k;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
cin>>a[i][j];
cin>>s;
// cout<<"done"<<endl;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
bfs(i,j);
int ans = 0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (ans += seen[0][i][j]);
cout<<ans<<endl;
}
Compilation message
nautilus.cpp: In function 'void deal(int, int, int, char)':
nautilus.cpp:21:9: warning: array subscript has type 'char' [-Wchar-subscripts]
21 | i += x[d];
| ^
nautilus.cpp:22:9: warning: array subscript has type 'char' [-Wchar-subscripts]
22 | j += y[d];
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
4956 KB |
Output is correct |
2 |
Correct |
3 ms |
4956 KB |
Output is correct |
3 |
Correct |
3 ms |
4952 KB |
Output is correct |
4 |
Correct |
3 ms |
4952 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
2 ms |
4936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
4956 KB |
Output is correct |
2 |
Correct |
3 ms |
4956 KB |
Output is correct |
3 |
Correct |
3 ms |
4952 KB |
Output is correct |
4 |
Correct |
3 ms |
4952 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
2 ms |
4936 KB |
Output is correct |
7 |
Execution timed out |
1059 ms |
3544 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
4956 KB |
Output is correct |
2 |
Correct |
3 ms |
4956 KB |
Output is correct |
3 |
Correct |
3 ms |
4952 KB |
Output is correct |
4 |
Correct |
3 ms |
4952 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
2 ms |
4936 KB |
Output is correct |
7 |
Execution timed out |
1059 ms |
3544 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |