摘要：
单元油田可以通过上，下，左或右连通。在一个单元油田里架设一台采油机，它可以把和该单元油田相连的单元油田的石油采完。Input先输入2个正整数n，m。接着有n行，每行有m个字符。输入到文件结束。Output对于每组测试，输出最少需要架设几台采油机。q.empty()){26now=q.front();27q.pop();28for{29x=now.x+dir[i][0];30y=now.y+dir[i][1];31if32continue;33temp.x=x;34temp.y=y;35map[x][y]='*';36q.push;37}38}39}4041intmain(){42inti,j,n,m,count;43while{44count=0;45for{46scanf;47for48map[i][j]=str[j-1];49}50for51for52if{53bfs;54count++;55}56printf;57}58return0;59}ViewCodeDFS:1#include2#include3usingnamespacestd;4constintN=55;5intn,m;6chars[N][N];7intvist[N][N];8intdir[][2]={-1,0,0,1,1,0,0,-1};//代表上下左右四个方向9voiddfs10{11vist[x][y]=1;12for13{14intnx=x+dir[d][0];15intny=y+dir[d][1];16if17{18dfs;19}20}21}22intmain()23{24while25{26intsum=0;27memset;28for29{30for31{32cin>>s[i][j];33}34}35for36{37for38{39if40{41++sum;42dfs(i,j);43}44}45}46cout2#include3#include4#include5usingnamespacestd;67constintN=50;89chars[N][N];10boolvisit[N][N];1112intdx[]={-1,0,1,0};13intdy[]={0,1,0,-1};14intn,m;1516voiddfs{17visit[x][y]=1;18for{19intnx=x+dx[i];20intny=y+dy[i];21if22dfs;23}24}2526intmain(){27intcnt,i,j;28//ifstreamcin;29while{30cnt=0;31memset;//很重要32for33cin>>s[i];3435for36for{37if{38cnt++;39dfs(i,j);40}41}42cout
油田合并
TimeLimit: 1 Second MemoryLimit: 32 Megabyte
Totalsubmit: 603 Accepted: 166
Description
某石油公司发现了一个油田。该油田由n*m个单元组成的矩形，有些单元里有石油，有些则没有。单元油田可以通过上，下，左或右连通。在一个单元油田里架设一台采油机，它可以把和该单元油田相连的单元油田的石油采完。该公司想知道最少需要架设几台采油机能把所有的石油采完？
Input
先输入2个正整数n，m(1<=n,m<=50)。接着有n行，每行有m个字符。'@'表示该单元有石油，'*'则表示该单元没有石油。 输入到文件结束。Output
对于每组测试，输出最少需要架设几台采油机。Sample Input
2 2
@*
*@
2 2
@@
@@
Sample Output
2 1
BFS:
1 /*简单BFS搜索*/ 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 6 7 using namespacestd; 8 9 structQ{ 10 intx,y; 11 }; 12 13 int dir[4][2]={1,0,-1,0,0,1,0,-1}; 14 char map[105][105]; 15 char str[105]; 16 17 void bfs(int a,int b,int n,intm){ 18 inti,x,y; 19 queue<Q>q; 20 Q now,temp; 21 temp.x=a; 22 temp.y=b; 23 map[a][b]='*'; 24 q.push(temp); 25 while(!q.empty()){ 26 now=q.front(); 27 q.pop(); 28 for(i=0;i<4;i++){ 29 x=now.x+dir[i][0]; 30 y=now.y+dir[i][1]; 31 if(x<1||x>n||y<1||y>m||map[x][y]=='*') 32 continue; 33 temp.x=x; 34 temp.y=y; 35 map[x][y]='*'; 36 q.push(temp); 37 } 38 } 39 } 40 41 intmain(){ 42 inti,j,n,m,count; 43 while(~scanf("%d%d",&n,&m)&&m){ 44 count=0; 45 for(i=1;i<=n;i++){ 46 scanf("%s",str); 47 for(j=1;j<=m;j++) 48 map[i][j]=str[j-1]; 49 } 50 for(i=1;i<=n;i++) 51 for(j=1;j<=m;j++) 52 if(map[i][j]=='@'){ 53 bfs(i,j,n,m); 54 count++; 55 } 56 printf("%d ",count); 57 } 58 return 0; 59 }
DFS:
1 #include<iostream> 2 #include<cstring> 3 using namespacestd; 4 const int N=55; 5 intn,m; 6 chars[N][N]; 7 intvist[N][N]; 8 int dir[][2]={-1,0,0,1,1,0,0,-1};//代表上下左右四个方向 9 void dfs(int x,inty) 10 { 11 vist[x][y]=1; 12 for(int d=0;d<4;++d) 13 { 14 int nx=x+dir[d][0]; 15 int ny=y+dir[d][1]; 16 if(nx<=n&&s[nx][ny]=='@'&&vist[nx][ny]==0) 17 { 18 dfs(nx,ny); 19 } 20 } 21 } 22 intmain() 23 { 24 while(cin>>n>>m) 25 { 26 int sum=0; 27 memset(vist,0,sizeof(vist)); 28 for(int i=1;i<=n;++i) 29 { 30 for(int j=1;j<=m;++j) 31 { 32 cin>>s[i][j]; 33 } 34 } 35 for(int i=1;i<=n;++i) 36 { 37 for(int j=1;j<=m;++j) 38 { 39 if(vist[i][j]==0&&s[i][j]=='@') 40 { 41 ++sum; 42 dfs(i,j); 43 } 44 } 45 } 46 cout<<sum<<endl; 47 } 48 return 0; 49 }
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <fstream> 5 using namespacestd; 6 7 const int N = 50; 8 9 chars[N][N]; 10 boolvisit[N][N]; 11 12 int dx[] = {-1, 0, 1, 0}; 13 int dy[] = {0, 1, 0, -1}; 14 intn, m; 15 16 void dfs(int x, inty){ 17 visit[x][y] = 1; 18 for(int i = 0; i < 4; i++){ 19 int nx = x +dx[i]; 20 int ny = y +dy[i]; 21 if(nx >= 0 && nx < n && ny >= 0 && ny < m && visit[nx][ny] == 0 && s[nx][ny] == '@') 22 dfs(nx, ny); 23 } 24 } 25 26 intmain(){ 27 intcnt, i, j; 28 //ifstream cin("a.txt"); 29 while(cin >> n >>m){ 30 cnt = 0; 31 memset(visit, 0, sizeof(visit));//很重要 32 for(i = 0; i < n; i++) 33 cin >>s[i]; 34 35 for(i = 0; i < n; i++) 36 for(j = 0; j < m; j++){ 37 if(visit[i][j] == 0 && s[i][j] == '@'){ 38 cnt++; 39 dfs(i, j); 40 } 41 } 42 cout << cnt <<endl; 43 } 44 //system("pause"); 45 }