Information
- ID
- 207
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 3
- Tags
- # Submissions
- 92
- Accepted
- 20
- Uploaded By
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char g[N][N];
int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};
bool st[N][N];
int n,m;
struct Node{
int x,y;
};
void bfs(int x,int y)
{
queue<Node> q;
q.push({x,y});
st[x][y]=1;
while(q.size())
{
Node t=q.front();
q.pop();
int x=t.x,y=t.y;
for(int i=0;i<8;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0||a>=n||b<0||b>=m)
{
continue;
}
if(g[a][b]=='.')
{
continue;
}
if(st[a][b])
{
continue;
}
st[a][b]=1;
q.push({a,b});
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>g[i];
}
int res=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(g[i][j]=='W'&&!st[i][j])
{
bfs(i,j);
res++;
}
}
}
cout<<res;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=120;
int dx[]={-1,0,1,-1,1,-1,0,1};
int dy[]={-1,-1,-1,0,0,1,1,1};
char g[N][N];
int n,m;
bool cnt[N][N];
struct node{int x,y;};
void bfs(int x,int y)
{
cnt[x][y]=1;
queue<node>q;
q.push({x,y});
while(q.size())
{
node t=q.front();
q.pop();
for(int i=0;i<8;i++)
{
int a=t.x+dx[i],b=t.y+dy[i];
if(g[a][b]=='.')
{
continue;
}
if(a<1||a>n||b<1||b>m)
{
continue;
}
if(cnt[a][b])
{
continue;
}
q.push({a,b});
cnt[a][b]=1;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
}
}
int res=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(g[i][j]=='W'&&!cnt[i][j])
{
bfs(i,j);
res++;
}
}
}
cout<<res;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char g[N][N];
int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};
bool st[N][N];
int n,m;
struct Node
{
int x,y;
};
void bfs(int x,int y)
{
queue<Node> q;
q.push({x,y});
st[x][y]=1;
while(q.size())
{
Node t=q.front();
q.pop();
int x=t.x,y=t.y;
for(int i=0;i<8;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0 || a>=n || b<0 || b>=m)
{
continue;
}
if(g[a][b]=='.')
{
continue;
}
if(st[a][b])
{
continue;
}
st[a][b]=1;
q.push({a,b});
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>g[i];
}
int res=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(g[i][j]=='W' && !st[i][j])
{
bfs(i,j);
res++;
}
}
}
cout<<res;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};
struct PII{
int x,y;
};
const int N=150;
char g[N][N];
bool st[N][N];
int n,m;
void bfs(int x,int y)
{
queue<PII> q;
q.push({x,y});
st[x][y]=1;
while(q.size())
{
PII t=q.front();
q.pop();
for(int i=0;i<8;i++)
{
int a=t.x+dx[i],b=t.y+dy[i];
if(a<1||a>n||b<1||b>m) continue;
if(g[a][b]=='.') continue;
if(st[a][b]) continue;
q.push({a,b});
st[a][b]=1;
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
}
}
int cnt=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(st[i][j]==0&&g[i][j]=='W')
{
cnt++;
bfs(i,j);
}
}
}
cout<<cnt;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char g[N][N];
vector<int> dx[N]={0,-1,1,0,1,0,-1,1};
vector<int> dy[N]={0,-1,1,-1,-1,0,0,1};
int n,m,st[N][N];
struct Node{
int x,y;
};
bool bfs(int x,int y,int q[N])
{
q.push({x,-1});
q.push({y,-1});
st[0][0]=0;
while(--q.size())
{
Node t=q.size();
int f=q.top();
int x=f.x,y=f.y;
for(int i=1;i<=q.x;i++)
{
int a=x+q[i],b=y+q[i];
if(x<0||a>=n||b<0||b>=m) break;
if(st[a][b]=='M') break;
if(q[a][b]) break;
q[0][1]=1;
q.push({-1,x});
q.push({-1,y});
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>g[i];
int res;
for(int i=0;i<n>>1;i++)
{
for(int j=i;j<m/i;j++)
{
if(st[i][j]=='W'&&q[i][j])
{
bfs(q,res);
res--;
}
}
res++;
}
cout<<res;
return 0;
}