#include <bits/stdc++.h>
#define foreach for
#define in :
using namespace std;
typedef long long ll;
/*
Konichiwa
Konichiwa
Ara ~~ ara
Bob no taisuki - Shinobu Kocho
* * * * *
* *
* *
* * I love SHINOBU <3 <3 <3
* *
* *
* * * * *
*/
/*
_________________________
Author : Bob15324
_________________________
*/
template<class X , class Y>
bool Minimize(X & x , Y y)
{
if(x == -1 || x >y)
{
x = y;
return true;
}
return false;
}
template<class X , class Y>
bool Maximize(X & x , Y y)
{
if( x < y)
{
x = y;
return true;
}
return false;
}
/* End of templates. Let's see what do we have here */
int n , m , k;
char a[501][501];
string s;
struct TrangThai
{
int i , j , kay;
TrangThai()
{
}
TrangThai(int _i , int _j , int _kay)
{
i = _i;
j = _j;
kay = _kay;
}
};
map<char , pair<int ,int >>diction;
map<pair<pair<int ,int > , int > , bool>dict;
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , -1 , 1};
int main()
{
ios_base :: sync_with_stdio(0);cin.tie(0);
diction['W'] = make_pair(0 , -1);
diction['S'] = make_pair(1 , 0);
diction['E'] = make_pair(0 , 1);
diction['N'] = make_pair(-1 , 0);
cin >> n >> m >> k;
for(int i =1 ; i <= n ; i++ )
{
for(int j =1; j <= m ; j++)
{
cin >> a[i][j];
}
}
cin >> s;
queue<TrangThai>q;
for(int i = 1; i <= n ; i ++)
{
for(int j = 1; j <= m ; j++)
{
if(a[i][j] =='.')
{
q.push(TrangThai(i , j , 0));
dict[make_pair(make_pair(i , j) , 0 )] = true;
}
}
}
int res = 0;
while(!q.empty())
{
TrangThai _trangthai = q.front();
q.pop();
int i = _trangthai.i;
int j = _trangthai.j;
int kay = _trangthai.kay;
if(kay == (int)s.size() + 1)
{
res++;
continue;
}
if(s[kay] != '?')
{
int x = i + diction[s[kay]].first;
int y = j + diction[s[kay]].second;
if(x < 1 || x > n || y < 1 || y > m)
{
continue;
}
if(a[x][y] =='#' || dict[make_pair( make_pair(x , y), kay + 1)])
{
continue;
}
dict[make_pair( make_pair(x , y), kay + 1)] = true;
q.push(TrangThai(x , y , kay + 1));
continue;
}
for(int z = 0 ; z < 4 ; z++)
{
int x = i + dx[z];
int y = j + dy[z];
if(x < 1 || x > n || y < 1 || y > m)
{
continue;
}
if(a[x][y] =='#' || dict[make_pair( make_pair(x , y), kay + 1)])
{
continue;
}
dict[make_pair( make_pair(x , y), kay + 1)] = true;
q.push(TrangThai(x , y , kay + 1));
}
}
cout << res;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
323 ms |
57036 KB |
Output is correct |
2 |
Correct |
20 ms |
4052 KB |
Output is correct |
3 |
Correct |
5 ms |
1472 KB |
Output is correct |
4 |
Correct |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
323 ms |
57036 KB |
Output is correct |
2 |
Correct |
20 ms |
4052 KB |
Output is correct |
3 |
Correct |
5 ms |
1472 KB |
Output is correct |
4 |
Correct |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
563 ms |
62732 KB |
Output is correct |
8 |
Correct |
96 ms |
11532 KB |
Output is correct |
9 |
Correct |
18 ms |
2880 KB |
Output is correct |
10 |
Correct |
6 ms |
1108 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
731 ms |
63932 KB |
Output is correct |
13 |
Correct |
821 ms |
47476 KB |
Output is correct |
14 |
Correct |
419 ms |
29884 KB |
Output is correct |
15 |
Correct |
11 ms |
1876 KB |
Output is correct |
16 |
Correct |
2 ms |
636 KB |
Output is correct |
17 |
Correct |
835 ms |
64408 KB |
Output is correct |
18 |
Correct |
654 ms |
51784 KB |
Output is correct |
19 |
Correct |
207 ms |
22812 KB |
Output is correct |
20 |
Correct |
68 ms |
8232 KB |
Output is correct |
21 |
Correct |
3 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
323 ms |
57036 KB |
Output is correct |
2 |
Correct |
20 ms |
4052 KB |
Output is correct |
3 |
Correct |
5 ms |
1472 KB |
Output is correct |
4 |
Correct |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
563 ms |
62732 KB |
Output is correct |
8 |
Correct |
96 ms |
11532 KB |
Output is correct |
9 |
Correct |
18 ms |
2880 KB |
Output is correct |
10 |
Correct |
6 ms |
1108 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
731 ms |
63932 KB |
Output is correct |
13 |
Correct |
821 ms |
47476 KB |
Output is correct |
14 |
Correct |
419 ms |
29884 KB |
Output is correct |
15 |
Correct |
11 ms |
1876 KB |
Output is correct |
16 |
Correct |
2 ms |
636 KB |
Output is correct |
17 |
Correct |
835 ms |
64408 KB |
Output is correct |
18 |
Correct |
654 ms |
51784 KB |
Output is correct |
19 |
Correct |
207 ms |
22812 KB |
Output is correct |
20 |
Correct |
68 ms |
8232 KB |
Output is correct |
21 |
Correct |
3 ms |
596 KB |
Output is correct |
22 |
Execution timed out |
1105 ms |
237432 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |