#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<char>>grid;
vector<vector<bool>>visitado;
vector<vector<bool>>vact;
bool bfs(int n, int m, char tipo) {
bool corte=false;
queue<pair<int,int>>colaBFS;
vact.clear();
vact.assign(n, vector<bool>(m, 0));
colaBFS.push(make_pair(0,0));
visitado[0][0]=true;
vact[0][0]=true;
while(!colaBFS.empty()) {
int i=colaBFS.front().first;
int j=colaBFS.front().second;
colaBFS.pop();
if (i+1<n){
if (!visitado[i+1][j]){
if (grid[i+1][j]!='.' and grid[i+1][j]!=tipo) corte=true;
else if (grid[i+1][j]==tipo){
visitado[i+1][j]=true;
vact[i+1][j]=true;
colaBFS.push(make_pair(i+1, j));
}
}else if (!vact[i+1][j]){
vact[i+1][j]=true;
colaBFS.push(make_pair(i+1, j));
}
}if (i-1>=0){
if (!visitado[i-1][j]){
if (grid[i-1][j]!='.' and grid[i-1][j]!=tipo) corte=true;
else if (grid[i-1][j]==tipo){
visitado[i-1][j]=true;
vact[i-1][j]=true;
colaBFS.push(make_pair(i-1, j));
}
}else if (!vact[i-1][j]){
vact[i-1][j]=true;
colaBFS.push(make_pair(i-1, j));
}
}if (j+1<m){
if (!visitado[i][j+1]){
if (grid[i][j+1]!='.' and grid[i][j+1]!=tipo) corte=true;
else if (grid[i][j+1]==tipo){
visitado[i][j+1]=true;
vact[i][j+1]=true;
colaBFS.push(make_pair(i, j+1));
}
}else if (!vact[i][j+1]){
vact[i][j+1]=true;
colaBFS.push(make_pair(i, j+1));
}
}if (j-1>=0){
if (!visitado[i][j-1]){
if (grid[i][j-1]!='.' and grid[i][j-1]!=tipo) corte=true;
else if (grid[i][j-1]==tipo){
visitado[i][j-1]=true;
vact[i][j-1]=true;
colaBFS.push(make_pair(i, j-1));
}
}else if (!vact[i][j-1]){
vact[i][j-1]=true;
colaBFS.push(make_pair(i, j-1));
}
}
}return corte;
}
int main(){
int n, m;
cin>>n>>m;
grid.resize(n, vector<char>(m));
visitado.resize(n, vector<bool>(m, false));
for (int i=0; i<n; i++){
for (int j=0; j<m; j++) cin>>grid[i][j];
}int animals=0;
char tipo=grid[0][0];
while (true){
animals++;
if (bfs(n, m, tipo)==false) break;
if (tipo=='F') tipo='R';
else tipo='F';
}cout<<animals<<endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
101 ms |
892 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
15 ms |
704 KB |
Output is correct |
| 5 |
Correct |
45 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
2 ms |
340 KB |
Output is correct |
| 10 |
Correct |
44 ms |
468 KB |
Output is correct |
| 11 |
Correct |
4 ms |
340 KB |
Output is correct |
| 12 |
Correct |
33 ms |
520 KB |
Output is correct |
| 13 |
Correct |
44 ms |
440 KB |
Output is correct |
| 14 |
Correct |
50 ms |
468 KB |
Output is correct |
| 15 |
Correct |
252 ms |
908 KB |
Output is correct |
| 16 |
Correct |
104 ms |
904 KB |
Output is correct |
| 17 |
Correct |
259 ms |
880 KB |
Output is correct |
| 18 |
Correct |
14 ms |
596 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1447 ms |
1108 KB |
Output is correct |
| 2 |
Execution timed out |
2039 ms |
3892 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2045 ms |
33100 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2081 ms |
8788 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2083 ms |
20388 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2103 ms |
31200 KB |
Time limit exceeded |
| 7 |
Correct |
1050 ms |
1120 KB |
Output is correct |
| 8 |
Correct |
1446 ms |
1100 KB |
Output is correct |
| 9 |
Correct |
79 ms |
340 KB |
Output is correct |
| 10 |
Correct |
210 ms |
344 KB |
Output is correct |
| 11 |
Correct |
453 ms |
1116 KB |
Output is correct |
| 12 |
Correct |
1051 ms |
348 KB |
Output is correct |
| 13 |
Execution timed out |
2082 ms |
3900 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2068 ms |
2412 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2081 ms |
2616 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2071 ms |
1740 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2073 ms |
9520 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2069 ms |
9292 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2078 ms |
8788 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2065 ms |
8040 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2078 ms |
21164 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2073 ms |
20384 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2076 ms |
17612 KB |
Time limit exceeded |
| 24 |
Execution timed out |
2071 ms |
20660 KB |
Time limit exceeded |
| 25 |
Execution timed out |
2017 ms |
32888 KB |
Time limit exceeded |
| 26 |
Correct |
639 ms |
26776 KB |
Output is correct |
| 27 |
Correct |
1675 ms |
31012 KB |
Output is correct |
| 28 |
Execution timed out |
2089 ms |
31128 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2021 ms |
31196 KB |
Time limit exceeded |
| 30 |
Correct |
1917 ms |
30664 KB |
Output is correct |
| 31 |
Execution timed out |
2076 ms |
23488 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2101 ms |
31052 KB |
Time limit exceeded |
