#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using ordered_set=tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef map<int, int> mii;
typedef map<ll, ll> mll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;i>=(a);--i)
#define R0F(i,a)ROF(i,0,a)
#define trav(a,x)for (auto& a: x)
#define sz(x) (long long)(x).size()
#define mp make_pair
#define pb push_back
#define bsearch binary_search
#define f first
#define s second
#define resz resize
#define rall(x) x.rbegin(), x.rend()
#define lb lower_bound
#define ub upper_bound
#define ender cout<<'\n';
#define google(x) cout<<"CASE #"<<x<<": ";
#define all(x) x.begin(), x.end()
#define ins insert
#define eb emplace_back
const ll MOD = 1e9+7;
const int MX=1000001;//1e5+1
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
cin.sync_with_stdio(0); cin.tie(0); // fast I/O
// cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int
if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
char board[3000][3000];
ll n, k;
bool visited[3000][3000];
void dfs(ll x, ll y){
if(x<1 or x>n or y<1 or y>k or visited[x][y] or board[x][y]!='*'){
return;
}
visited[x][y]=1;
dfs(x+1, y);
dfs(x, y-1);
dfs(x-1, y);
dfs(x, y+1);
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
cin>>board[i][j];
}
}
ll answer=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
if(!visited[i][j] && board[i][j]=='*'){
++answer;dfs(i, j);
}
}
}
cout<<answer<<'\n';
}
Compilation message
emacs.cpp: In function 'void setIn(std::__cxx11::string)':
emacs.cpp:47:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
~~~~~~~^~~~~~~~~~~~~~~~~~~~~
emacs.cpp: In function 'void setOut(std::__cxx11::string)':
emacs.cpp:48:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
896 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1152 KB |
Output is correct |
| 3 |
Correct |
6 ms |
896 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1152 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1024 KB |
Output is correct |
