抠图(DFS)
蒜头君在做图像处理的项目时，遇到了一个问题。他需要摘取出图片中，某个黑色线框内的图片，现在请你来帮助他完成这一步，把黑色线框外的区域全部变为黑色，即只保留黑色线框内的颜色。
蒜头君可能同时摘取多个线框，这些线框不会出现相邻，相交，包含关系，因为选择线框太多，所以蒜头君可能把其中一部分的线框少画一条边，所以这种线框是无效的。
已知图中除了黑线上的点外，图像中没有纯黑色（即像素为 00 的点）。
矩形关系说明：
其中下面的数据也属于相邻。
0 0 0 1 1 1
0 1 0 1 1 1
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 0 1 0
1 1 1 0 0 0
也就是说 00 的周围（八个方向），不会有另外一个矩形的 00。
输入格式
第一行输入测试数据的组数 N(0 < N \le 10)N(0<N≤10)。
每组测试数据的第一行是两个整数 H,WH,W 分别表示图片的高度和宽度 (3 \le H,W \le 500)(3≤H,W≤500)。
随后的 HH 行，每行有 WW 个正整数，表示该点的像素值。(像素值都在 00 到 255255 之间，00 表示黑色，255255 表示白色），每行整数之间使用'\t'隔开。
输出格式
以矩阵形式输出，先把黑色框之外的区域变黑，然后输出图像中各点的像素值。
数据约定
对于 30\%30% 的数据，线框是宽度为 11 的矩形，并且线框都是完整的。
对于 60\%60% 的数据，线框是宽度不固定的的矩形，并且线框都是完整的。
对于 100\%100% 的数据，线框可能有多个（题目保证线框不会出现相邻，相交，包含关系），线框是宽度不固定，有部分线框可能缺失其中的一条边（可以认为这种线框为无效线框）。
样例解释
对于第一组数据：
这是一个完整的矩形，所以会保留线框内的颜色，保留下 (3,2),(3,3)(3,2),(3,3) 的像素值。
对于第二组数据：
只有一个矩形，这个矩形不是完成整的矩形，所有是无效线框，所以没有像素值被保留。
对于第三组数据：
有多个矩形，且矩形都满足不相邻，相交，包含的关系。
样例输入复制
3 4 5 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 5 6 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 10 10 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0
样例输出复制
0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
题目来源
解析:
从四周找连通块,对于不完整的长方体,自然能把里面的给变成0,用dfs或者bfs都可以
注意大于0就是白色,不仅仅是1
ac:
#include<bits/stdc++.h>
#define MAXN 505
using namespace std;
int tx[4]={0,1,0,-1};
int ty[4]={1,0,-1,0};
int n,m;
int mp[MAXN][MAXN];
int vis[MAXN][MAXN];
void dfs(int x,int y)
{
mp[x][y]=0;
for(int i=0;i<4;i++)
{
int dx=x+tx[i];
int dy=y+ty[i];
if(dx>=0&&dy>=0&&dx<n&&dy<m)
if(mp[dx][dy]>0)
dfs(dx,dy);
}
}
int main()
{
//freopen("E:/in.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
memset(mp,0,sizeof(mp));
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&mp[i][j]);
for(int i=0;i<m;i++)
{
if(mp[0][i]>0)
dfs(0,i);
if(mp[n-1][i]>0)
dfs(n-1,i);
}
for(int i=0;i<n;i++)
{
if(mp[i][0]>0)
dfs(i,0);
if(mp[i][m-1]>0)
dfs(i,m-1);
}
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
printf("%d",mp[i][j]);
if(j==m-1)
printf("\n");
else
printf(" ");
}
}
return 0;
}