图像有用区域（bfs）

图像有用区域

时间限制： 3000 ms  |  内存限制： 65535 KB 难度： 4

描述

“ACKing”同学以前做一个图像处理的项目时，遇到了一个问题，他需要摘取出图片中某个黑色线圏成的区域以内的图片，现在请你来帮助他完成第一步，把黑色线圏外的区域全部变为黑色。

                图1                                                        图2 

已知黑线各处不会出现交叉（如图2）,并且，除了黑线上的点外，图像中没有纯黑色（即像素为0的点）。

输入

第一行输入测试数据的组数N(0<N<=6)

每组测试数据的第一行是两个个整数W,H分表表示图片的宽度和高度(3<=W<=1440,3<=H<=960)

随后的H行，每行有W个正整数,表示该点的像素值。(像素值都在0到255之间，0表示黑色，255表示白色）

输出

以矩阵形式输出把黑色框之外的区域变黑之后的图像中各点的像素值。

样例输入

1
5 5
100 253 214 146 120
123 0 0 0 0
54 0 33 47 0
255 0 0 78 0
14 11 0 0 0
      

样例输出

0 0 0 0 0
0 0 0 0 0
0 0 33 47 0
0 0 0 78 0
0 0 0 0 0      

来源

[张云聪]原创

上传者

张云聪

因为此处的横坐标与纵坐标的与常规的不同，

定义的时候要注意

第二，将map的周围定义为不是黑色区域，便于bfs

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct node
{
	int x,y;
}st,ed;

int h,w;
int map[1450][1450];

void bfs()
{
	st.x=0;st.y=0;
	int next[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
	queue<node>Q;
	Q.push(st);
	while(!Q.empty())
	{
		st=Q.front();
		Q.pop();
		for(int i=0;i<4;i++)
		{
			ed.x=st.x+next[i][0];
			ed.y=st.y+next[i][1];
			if(ed.x<0||ed.x>h+1||ed.y<0||ed.y>w+1||map[ed.x][ed.y]==0)
			{
				continue;
			}
			map[ed.x][ed.y]=0;
			Q.push(ed);
		}
	}
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(map,0,sizeof(map));
		scanf("%d %d",&w,&h);
		for(int i=0;i<=w+1;i++)
		{
			map[0][i]=1;
			map[h+1][i]=1;
		}
		for(int j=0;j<=h+1;j++)
		{
			map[j][0]=1;
			map[j][w+1]=1;;
		}
		for(int i=1;i<=h;i++)
		{
			for(int j=1;j<=w;j++)
			{
				scanf("%d",&map[i][j]);
			}
		}
		
		bfs();
		for(int i=1;i<=h;i++)
		{
			for(int j=1;j<=w;j++)
			{
				if(j!=1)
				{
					printf(" ");
				}
				printf("%d",map[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}
           

不知为何，这个题目深搜老是runtime error，所以很奇怪，有机会debug一下

还要注意bfs与dfs的区别与选择，

类似这个题目与水池的数目都应该优先选择dfs......

其中很多用bfs的可能用dfs写出来像bfs

此处需要结合实际情况仔细分析