#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#define grid(n,m) for (ll i=1;i<=n;i++){for (ll j=1;j<=m;j++) cin>>graph[i][j];}
#define vll vector<ll>
#define qll queue<ll>
#define pll pair<ll,ll>
#define str string
#define pb push_back
#define ll long long
using namespace std;
const ll inf=2*1e5+1;
const ll graph_size=4000;
// Fast Input/Output
void fastio(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
}
// File Input/Output
str fileio(const string&filePath=__FILE__){
size_t lastSlash=filePath.find_last_of('/');
size_t lastDot=filePath.rfind('.');
return filePath.substr(lastSlash+1,lastDot-lastSlash-1);
}
ll n,m;
// Floodfill
ll row_num,col_num;
char graph[graph_size+2][graph_size+2];
vector<pll> directions={{0,-1},{-1,0},{1,0},{0,1}};
bool floodfill_visited[graph_size+2][graph_size+2];
bool seen[graph_size+2][graph_size+2];
vector<pll> path;
ll curr=0;
void floodfill_dfs(pll coord,char color){
ll x=coord.first;
ll y=coord.second;
if (x==3 and y==4){
ll z=1;
}
if ((graph[x][y]!=color and !seen[x][y]) or x<=0 or x>n or y<=0 or y>m or floodfill_visited[x][y]){
return;
}
floodfill_visited[x][y]=1;
if (!seen[x][y]){
curr++;
}
seen[x][y]=1;
path.pb({x,y});
for (auto i:directions){
floodfill_dfs({x+i.first,y+i.second},color);
}
}
ll floodfill_level[graph_size+2][graph_size+2];
void floodfill_bfs(pll coord,char color){
ll x=coord.first;
ll y=coord.second;
queue<pair<ll,ll>> Q;
Q.push({x,y});
floodfill_level[x][y]=0;
while (!Q.empty()){
pll curr=Q.front();
Q.pop();
x=curr.first;
y=curr.second;
floodfill_visited[x][y]=1;
for (auto i:directions){
if (graph[x+i.first][y+i.second]==color and x+i.first>=1 and x+i.first<=n and y+i.second>=1 and y+i.second<=n){
floodfill_level[x+i.first][y+i.second]=floodfill_level[x][y]+1;
Q.push({x+i.first,y+i.second});
}
}
}
}
int main(){
// auto start_time=chrono::steady_clock::now();
fastio();
// str filename=fileio();
// ifstream cin(filename+".in");
// ofstream cout(filename+".out");
ll t=1;
// cin>>t;
while (t--){
cin>>n>>m;
grid(n,m);
ll tracks=0;
for (ll i=1;i<=n;i++){
for (ll j=1;j<=m;j++){
if (graph[i][j]!='.'){
tracks++;
}
}
}
char animal=graph[1][1];
ll ans=0;
while (curr<tracks){
ans++;
floodfill_dfs({n,m},animal);
for (auto i:path){
floodfill_visited[i.first][i.second]=0;
}
path.clear();
if (animal=='F'){
animal='R';
}
else{
animal='F';
}
}
cout<<ans<<"\n";
}
// auto end_time=chrono::steady_clock::now();
// auto elapsed_time=chrono::duration_cast<chrono::milliseconds>(end_time-start_time);
// cout<<"Elapsed time: "<<elapsed_time.count()<<" milliseconds\n";
}
Compilation message
tracks.cpp: In function 'void floodfill_dfs(std::pair<long long int, long long int>, char)':
tracks.cpp:39:12: warning: unused variable 'z' [-Wunused-variable]
39 | ll z=1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
385 ms |
30228 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4696 KB |
Output is correct |
| 4 |
Correct |
33 ms |
23248 KB |
Output is correct |
| 5 |
Correct |
80 ms |
6884 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4456 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4712 KB |
Output is correct |
| 8 |
Correct |
2 ms |
5308 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4968 KB |
Output is correct |
| 10 |
Correct |
104 ms |
6820 KB |
Output is correct |
| 11 |
Correct |
9 ms |
9188 KB |
Output is correct |
| 12 |
Correct |
109 ms |
13016 KB |
Output is correct |
| 13 |
Correct |
88 ms |
7148 KB |
Output is correct |
| 14 |
Correct |
75 ms |
7156 KB |
Output is correct |
| 15 |
Correct |
803 ms |
20460 KB |
Output is correct |
| 16 |
Correct |
435 ms |
30220 KB |
Output is correct |
| 17 |
Correct |
643 ms |
16324 KB |
Output is correct |
| 18 |
Correct |
34 ms |
22880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2057 ms |
47416 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2053 ms |
37500 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2054 ms |
60864 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2029 ms |
48472 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2040 ms |
44704 KB |
Time limit exceeded |
| 6 |
Runtime error |
1823 ms |
1048576 KB |
Execution killed with signal 9 |
| 7 |
Correct |
1972 ms |
48732 KB |
Output is correct |
| 8 |
Execution timed out |
2065 ms |
47028 KB |
Time limit exceeded |
| 9 |
Correct |
245 ms |
7120 KB |
Output is correct |
| 10 |
Correct |
439 ms |
5516 KB |
Output is correct |
| 11 |
Correct |
735 ms |
47640 KB |
Output is correct |
| 12 |
Correct |
1481 ms |
6276 KB |
Output is correct |
| 13 |
Execution timed out |
2100 ms |
38904 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2037 ms |
29892 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2052 ms |
16996 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2062 ms |
28604 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2036 ms |
64216 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2095 ms |
31820 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2041 ms |
49668 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2054 ms |
27728 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2021 ms |
50240 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2047 ms |
48288 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2053 ms |
74988 KB |
Time limit exceeded |
| 24 |
Execution timed out |
2031 ms |
49488 KB |
Time limit exceeded |
| 25 |
Execution timed out |
2027 ms |
64280 KB |
Time limit exceeded |
| 26 |
Runtime error |
1043 ms |
1048576 KB |
Execution killed with signal 9 |
| 27 |
Runtime error |
1485 ms |
1048576 KB |
Execution killed with signal 9 |
| 28 |
Runtime error |
1656 ms |
1048576 KB |
Execution killed with signal 9 |
| 29 |
Runtime error |
1540 ms |
1048576 KB |
Execution killed with signal 9 |
| 30 |
Runtime error |
1106 ms |
1048576 KB |
Execution killed with signal 9 |
| 31 |
Execution timed out |
2025 ms |
276752 KB |
Time limit exceeded |
| 32 |
Runtime error |
1028 ms |
1048576 KB |
Execution killed with signal 9 |
