题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1241
题目大意:求一张地图里的连通块。注意可以斜着连通。
解题思路:
八个方向dfs一遍,一边dfs一边染色,断了之后换新颜色。
做法类似Tarjan。orz,我是不是刷错顺序了。
#include "cstdio"
#include "cstring"
#include "iostream"
#include "string"
using namespace std;
int n,m,map[][],vis[][],dir[][]={-,,,,,-,,,-,-,-,,,-,,},ans;
void dfs(int x,int y)
{
vis[x][y]=ans;
for(int s=;s<;s++)
{
int X=x+dir[s][],Y=y+dir[s][];
if(vis[X][Y]||X<||X>n||Y<||Y>m||!map[X][Y]) continue;
dfs(X,Y);
}
}
int main()
{
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
string tt;
while(cin>>n>>m&&n)
{
memset(vis,,sizeof(vis));
ans=;
for(int i=;i<=n;i++)
{
cin>>tt;
for(int j=;j<tt.size();j++)
{
if(tt[j]=='*') map[i][j+]=;
if(tt[j]=='@') map[i][j+]=;
}
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(map[i][j]&&!vis[i][j]) {ans++;dfs(i,j);}
cout<<ans<<endl;
}
}
11867645 | 2014-10-13 23:58:06 | Accepted | 1241 | 15MS | 400K | 992 B | C++ | Physcal |