## Question

The array is indexed first by row, then by column. Every row in the array will be the same length. Every element in the array will be non-negative and no greater than 255. A value of 0 represents a black pixel, and a value of 255 represents white, with shades of grey in between. Time complexity specifications use R for number of rows, C for number of columns, and P = R*C for number of pixels. public int floodFillCount(int[][] image, int row, int col)

Compute the number of pixels that change when performing a black flood-fill from the pixel at ( row , col ) in the given image. A flood-fill operation changes the selected pixel and all contiguous pixels of the same colour to the specified colour. A pixel is considered part of a contiguous region of the same colour if it is exactly one pixel up/down/left/right of another pixel in the region.

Compute the total brightness of the brightest exactly k*k square that appears in the given image. The total brightness of a square is defined as the sum of its pixel values. You may assume that k is positive, no greater than R or C , and no greater than 2048.

Compute the maximum brightness that MUST be encountered when drawing a path from the pixel at ( ur , uc ) to the pixel at ( vr , vc ). The path must start at ( ur , uc ) and end at ( vr , vc ), and may only move one pixel up/down/left/right at a time in between. The brightness of a path is considered to be the value of the brightest pixel that the path ever touches. This includes the start and end pixels of the path.

Compute the results of a list of queries on the given image. Each query will be a three-element int array {r, l, u} defining a row segment. You may assume l < u . A row segment is a set of pixels ( r , c ) such that r is as defined, l <= c , and c < u . For each query, find the value of the brightest pixel in the specified row segment. Return the query results in the same order as the queries are given.

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

Image processing assignment1. Black-flood fill count

The function is implemented in the method public int floodFillCount(int[][] image, int row, int col) from the class MyProject.

To solve this problem, I’ve used Breadth First Search (BFS) from the seed point (col, row).

I consider the image as a graph, with R*C vertices (meaning that each pixel in the image is considered as a vertex in the graph).

For simplicity, I also defined a Point class (in the file Point.java) to store the x, y coordinates of a pixel.

Each vertex crt from the graph is connected to 4 other vertices ( its adjacent north (N), south(S), east (E) and west (W) pixels):

N

W crt E

S

To determine the neighbours of a pixel, I used the following idea: I defined two arrays of displacements dx - for the horizontal displacements, and dy - for the vertical displacements.

// bottom: pt + (0, 1), right: pt + (1, 0), top: pt + (0, -1), left: pt + (-1, 0)

int dx[] = {0, 1, 0, -1};

int dy[] = {1, 0, -1, 0};

To obtain the neighbours of the pixel, I simply iterate through the displacements vector, and add these displacement values to the x and y locations of the pixel. Let’s say we have the a pixel at location Point crt = new Point(10, 10);

The neighbours of this pixel would be:

Point south = new Point(crt.getX() + dx[0], crt.getY() + dy[0]);

Point east = new Point(crt.getX() + dx[1], crt.getY() + dy[1]);

Point north = new Point(crt.getX() + dx[2], crt.getY() + dy[2]);

Point west = new Point(crt.getX() + dx[3], crt.getY() + dy[3]);

For the flood fill procedure, we need to find all the pixels with the same colour as the seed pixel which...

By purchasing this solution you'll be able to access the following files:

Solution.docx and Solution.zip.