nyoj 92 图片实用面积【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

分析：在原来的图上加一圈1.

代码：

#include <stdio.h>
#include <string.h>
#include <queue>
#define W 1445
#define H 965
using namespace std;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int map[H][W], w, h;
struct node{
	int x, y;
};

int limit(int x, int y){
	return (x>=0&&x<=h+1&&y>=0&&y<=w+1);  //这里的x。y。一定小于等于w+1，h+1；
} 

void bfs(){
	int i;
	node st;
	st.x = st.y = 0;
	queue<node > q;
	q.push(st);
	while(!q.empty()){
		node temp = q.front();
		for(i = 0; i < 4; i ++){
			node cur = temp;
			cur.x+=dx[i]; cur.y+=dy[i];
			if(map[cur.x][cur.y] == 0) continue;
			if(!limit(cur.x, cur.y)) continue;
			//if(cur.x < 0||cur.y <0||cur.x > h+1||cur.y > w+1 || map[cur.x][cur.y] == 0) continue;
			map[cur.x][cur.y] = 0;
			q.push(cur);
		}
		q.pop();
	}
}

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