Wednesday, September 7, 2016

UVA 572 - Oil Deposits

#include<bits/stdc++.h>
using namespace std;
int m , n , cnt;
vector<string>v;
string s;
bool vis[100][100];
int nx[8] = {1,1,1,-1,-1,-1,0,0};
int ny[8] = {1,0,-1,1,0,-1,1,-1};
void dfs(int start , int end)
{
vis[start][end] = 1;
int row , col;
for(int i=0; i<8; i++){
row = start + nx[i];
col = end + ny[i];
if(row >=0 && row<m && col>=0 && col<n && !vis[row][col]){
vis[row][col] = 1;
if(v[row][col] == '@')dfs(row,col);
}
}
}

int main()
{
while(cin>>m>>n && m){
v.clear();
for(int i=0; i<m; i++){
cin>>s;
v.push_back(s);
}
        cnt = 0;
        memset(vis,0,sizeof(vis));
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(!vis[i][j]){
vis[i][j] = true;
if(v[i][j] == '@'){cnt++; dfs(i,j);}
}
}
}
cout<<cnt<<'\n';
}

return 0;
}

No comments:

Post a Comment