#include <bits/stdc++.h>
#define ll long long
#define maxl LLONG_MAX
#define minl LLONG_MIN
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define bg begin()
#define nd end()
#define rnd(x) random_shuffle((x).begin, (x).end())
#define reverse(x) reverse((x).begin(), (x).end())
#define del erase
#define ssub substr
#define tp tuple
#define pp pop_back
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define vi vector<ll>
#define vii vector<pair<ll,ll>>
#define LSOne(x) (x&(-x))
#define log2(i) (__builtin_clzll(1) - __builtin_clzll(i))
#define gdc(a,b) __gcd(a,b)
#define lcm(a,b) ((a*b)/gdc(a,b))
#define dbg(x) (cerr<<"["<<"R"<<":"<<__LINE__<<"]"<<#x<<" -> "<<(x)<<'\n',(x))
#define rand (rand() * (RAND_MAX + 1) + rand()) % (int)1e6
#define count(x) __builtin_popcount(x)
//lower_bound(arr,arr+a,valore); unique() remove dups fill(vec,number) merge() binary_search()
//601 div2 b
using namespace std;
int n,m;
char mat[4000][4000];
bool vis[4000][4000];
bool valido(int i,int j){
if(i<0 || j<0 || i>=n || j>=m)return 0;
return 1;
}
void dfs(char (&mat)[4000][4000],int i,int j){
int c[]={1,-1,0,0};
int r[]={0,0,1,-1};
vis[i][j]=true;
for(int a=0;a<4;a++){
for(int b=0;b<4;b++){
if(valido(i+r[a],j+c[b])){
if(mat[i+r[a]][j+c[b]]==mat[i][j] || mat[i+r[a]][j+c[b]]==1 || mat[i][j]==1){
if(vis[i+r[a]][j+c[b]])continue;
dfs(mat,i+r[a],j+c[b]);
}
}
}
}
mat[i][j]=1;
}
void compute(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>mat[i][j];
// cout<<mat[i][j]<<" ";
}
// cout<<'\n';
}
int conta=1;
dfs(mat,n-1,m-1);
/* dfs(mat,0,2);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<mat[i][j]<<" ";
}
cout<<'\n';
}*/
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mat[i][j]!=1 && mat[i][j]!='.'){
// cout<<i<<" "<<j<<'\n';
memset(vis,0,sizeof(vis));
dfs(mat,i,j);
conta++;
}
}
}
cout<<conta;
}
int main(int argc, char** argv) {
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
t=1;
// cin>>t;
for(int i=1;i<=t;i++){
//cout<<"Case #"<<i<<": "<<compute()<<'\n';
compute();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
112 ms |
64336 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
16988 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
17240 KB |
Output isn't correct |
| 4 |
Correct |
67 ms |
47272 KB |
Output is correct |
| 5 |
Incorrect |
52 ms |
29424 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
16988 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
17244 KB |
Output isn't correct |
| 8 |
Incorrect |
6 ms |
17756 KB |
Output isn't correct |
| 9 |
Incorrect |
8 ms |
18012 KB |
Output isn't correct |
| 10 |
Incorrect |
22 ms |
31188 KB |
Output isn't correct |
| 11 |
Correct |
17 ms |
24412 KB |
Output is correct |
| 12 |
Incorrect |
29 ms |
24924 KB |
Output isn't correct |
| 13 |
Incorrect |
51 ms |
29520 KB |
Output isn't correct |
| 14 |
Incorrect |
57 ms |
29484 KB |
Output isn't correct |
| 15 |
Incorrect |
101 ms |
65976 KB |
Output isn't correct |
| 16 |
Incorrect |
109 ms |
64372 KB |
Output isn't correct |
| 17 |
Incorrect |
191 ms |
47444 KB |
Output isn't correct |
| 18 |
Correct |
67 ms |
47292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
34396 KB |
Output isn't correct |
| 2 |
Incorrect |
426 ms |
315932 KB |
Output isn't correct |
| 3 |
Execution timed out |
2132 ms |
796240 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2069 ms |
257760 KB |
Time limit exceeded |
| 5 |
Incorrect |
499 ms |
42548 KB |
Output isn't correct |
| 6 |
Runtime error |
1990 ms |
1048576 KB |
Execution killed with signal 9 |
| 7 |
Incorrect |
15 ms |
33372 KB |
Output isn't correct |
| 8 |
Incorrect |
17 ms |
34548 KB |
Output isn't correct |
| 9 |
Incorrect |
26 ms |
26960 KB |
Output isn't correct |
| 10 |
Incorrect |
9 ms |
21596 KB |
Output isn't correct |
| 11 |
Incorrect |
18 ms |
34724 KB |
Output isn't correct |
| 12 |
Incorrect |
6 ms |
17244 KB |
Output isn't correct |
| 13 |
Incorrect |
430 ms |
315744 KB |
Output isn't correct |
| 14 |
Incorrect |
259 ms |
191064 KB |
Output isn't correct |
| 15 |
Incorrect |
109 ms |
73552 KB |
Output isn't correct |
| 16 |
Incorrect |
236 ms |
138832 KB |
Output isn't correct |
| 17 |
Incorrect |
1071 ms |
790608 KB |
Output isn't correct |
| 18 |
Incorrect |
311 ms |
54096 KB |
Output isn't correct |
| 19 |
Execution timed out |
2084 ms |
251620 KB |
Time limit exceeded |
| 20 |
Incorrect |
1004 ms |
671132 KB |
Output isn't correct |
| 21 |
Runtime error |
1807 ms |
1048576 KB |
Execution killed with signal 9 |
| 22 |
Incorrect |
568 ms |
42576 KB |
Output isn't correct |
| 23 |
Runtime error |
1483 ms |
1048576 KB |
Execution killed with signal 9 |
| 24 |
Incorrect |
634 ms |
48964 KB |
Output isn't correct |
| 25 |
Incorrect |
1292 ms |
144064 KB |
Output isn't correct |
| 26 |
Runtime error |
707 ms |
1048576 KB |
Execution killed with signal 9 |
| 27 |
Execution timed out |
2146 ms |
1048576 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2009 ms |
1048576 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2096 ms |
1048576 KB |
Time limit exceeded |
| 30 |
Runtime error |
1264 ms |
1048576 KB |
Execution killed with signal 9 |
| 31 |
Runtime error |
1412 ms |
1048576 KB |
Execution killed with signal 9 |
| 32 |
Execution timed out |
2033 ms |
1048576 KB |
Time limit exceeded |
