Oil Deposits

小灰灰 2022-06-12 14:55 107阅读 0赞

[原题点这里][Link 1]

题意：算出一共多少块油田， 只要上下左右对角线相连就算一个。

思路：遍历每个点，只要是油田就以这个点深搜或者广搜， 将搜到的@变为 \* ，每调用一次就+1.

深搜：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=1e2+10;
    char _map[maxn][maxn];
    int m, n;
    int dir[8][2]={
       {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
    
    void DFS(int i, int j){
    	int x, y;
    	_map[i][j]='*';
    	for(int k=0; k<8; k++)
    	{
    		x=i+dir[k][0];
    		y=j+dir[k][1];
    		if(x<1 || x>m || y<1 || y>n || _map[x][y]=='*')
    			continue;
    		DFS(x, y);
    	}
    	return;
    }
    
    int main(){
    	int cnt;
    	while(scanf("%d%d", &m, &n) && m && n)
    	{
    		cnt=0;
    		for(int i=1; i<=m; i++)
    			cin>>_map[i]+1;//从——map[i]+1开始， 这个让我改了一晚上加一上午。T_T
    		
    		for(int i=1; i<=m; i++)
    			for(int j=1; j<=n; j++)
    			{
    				if(_map[i][j]=='*')
    					continue;
    				if(_map[i][j]=='@')
    				{
    					cnt++;
    					DFS(i, j);
    				}	
    					
    			}
    		cout<<cnt<<endl;
    	}
    	return 0;
    }

广搜：

#include<iostream>
    #include<cstring>
    #include<queue>
    #include<cstdio>
    using namespace std;
    const int maxn=1e2+10;
    int book[maxn][maxn];
    char _map[maxn][maxn];
    int dir[8][2]={
       {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}};
    
    struct node{
    	int x, y;
    }tmp, tmp1;
    
    int main(){
    	int m, n, cnt, x, y;
    	queue<struct node> q;
    	while(cin>>m>>n && m!=0)
    	{
    		cnt=0;
    		memset(book, 0, sizeof(book));
    		for(int i=1; i<=m; i++)
    			cin>>_map[i]+1;
    		for(int i=1; i<=m; i++)
    			for(int j=1; j<=n; j++)
    			{
    				if(_map[i][j]=='*' || book[i][j]==1)
    					continue;
    				if(book[i][j]==0 && _map[i][j]=='@')
    				{
    					cnt++;
    					tmp.x=i;
    					tmp.y=j;
    					q.push(tmp);
    					while(!q.empty())
    					{
    						tmp=q.front();
    						q.pop();
    						for(int k=0; k<8; k++)
    						{
    							x=tmp.x+dir[k][0];
    							y=tmp.y+dir[k][1];
    							if(x<1 || y<1 || x>m || y>n || _map[x][y]=='*' || book[x][y]==1)
    								continue;
    							
    							book[x][y]=1;
    							tmp1.x=x;
    							tmp1.y=y;
    							q.push(tmp1);
    							
    						}
    					}
    					 
    				}
    			}
    		cout<<cnt<<endl;
    	}
    	return 0;
    }

本人语拙，若有不懂，尽请留言，若有错误，不吝赐教。 喜欢博主的点波关注， 谢谢^\_^

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1241