栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

油区周长(c++,dfs)

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

油区周长(c++,dfs)

在一块土地上,某公司进行油田勘测,给出扫描图,统计包含某个有油点的油田的周长。当两个有油点相邻时,算一块油田(可以在8个方向上相邻)。

输入格式 输入文件名:you.in

第一行为正整数t(≤10),表示数据组数;每组数据中,第一行为四个正整数n,m,x,y;n,m(≤100)表示整个扫描图区域的长和宽,x(≤n),y(≤m)表示某有油点的坐标;接下来n行扫描图,每行m个字符,其中.表示无油点,X表示有油点。

输出格式 输出文件名:you.out

对于每组数据,输出相应油田区域的周长。

输入/输出例子1

输入:

2

7 7 2 6

XXXXXXX

XX...XX

X..X..X

X..X...

X..X..X

X.....X

XXXXXXX

7 7 4 4

XXXXXXX

XX...XX

X..X..X

X..X...

X..X..X

X.....X

XXXXXXX

输出:

48

8

code:

#include
using namespace std;
#define N 1005 
#define LL long long
LL n,m,t,x,y,dis[N][N];
LL fx_x[5]={1,1,-1,-1};
LL fx_y[5]={1,-1,1,-1};
char mp[N][N];
int dfs(int x,int y){
	if(dis[x][y]==1)return 0;
	if(mp[x][y]!='X')return 1;
	dis[x][y]=1;
    LL s=0;
    for(int i=0;i<4;i++)
		if(mp[x+fx_x[i]][y+fx_y[i]]=='X')s+=dfs(x+fx_x[i],y+fx_y[i]);
    return dfs(x+1,y)+dfs(x-1,y)+dfs(x,y+1)+dfs(x,y-1)+s;
}
int main(){
    freopen("you.in","r",stdin);
    freopen("you.out","w",stdout);
	cin>>t;
	while(t--){
		memset(mp,0,sizeof(mp));
		memset(dis,0,sizeof(dis));
        cin>>n>>m>>x>>y;
		for(int i=1;i<=n;i++)
	        for(int j=1;j<=m;j++)cin>>mp[i][j]; 
        cout< 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/928440.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号