Location>code7788 >text

BFS Color Fill - Rock Valley p1162

Popularity:922 ℃/2024-09-21 16:38:42

color filling

Title Description

digital\(0\) There is an arbitrary shape in the square formed by the number\(1\) The closed circle is formed. It is now required that all spaces within the closed circle be filled in with the\(2\). Example:\(6\times 6\) of the square (\(n=6\)), the squares before and after coloring are as follows:

If you start with one of the\(0\) Starting out, only up and down, left and right.\(4\) moves in one direction and passes only through the other\(0\) case cannot reach the boundary of the square, it is assumed that this\(0\) Inside the closing circle.. The closure ring does not have to be annular, it can be of any shape, but it is guaranteed that theInside the closed circle(used form a nominal expression)\(0\) are connected (two by two can reach each other).

0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 2 1
1 1 1 1 1 1

input format

One integer in the first row of each set of test data\(n(1 \le n \le 30)\)

accept\(n\) rows, by\(0\) cap (a poem)\(1\) constituent\(n \times n\) The squares.

There is only one closed circle within the square, and within the circle there is at least one\(0\)

output format

The numbers have been filled in.\(2\) The full square of the

Sample #1

Sample Input #1

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

Sample Output #1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

draw attention to sth.

insofar as\(100\%\) of the data.\(1 \le n \le 30\)

Problem analysis

This problem is clearly a search problem, to solve the search problem there are two commonly used methods BFS and DFS, if you use DFS will find that it will take a lot of time to backtrack, because we only need to mark the location we need to search can be, do not need to consider the order of the marking, so this problem I still prefer to use BFS
We only need to start from a point outside the circle, mark all the 0 outside the circle can be, so we need a fixed is outside the circle of the point, in the original picture does not seem to have this point, we can be in the circle outside the circle of another circle of 0 to open up the
coding

#include<iostream>;
#include<queue>
using namespace std.
int d[4][2] = { {0,-1},{0,1},{-1,0},{1,0} }; int a[50][50]; //A little more is good.
int a[50][50]; // more openings are allowed
int n; queue<pair<
queue<pair<int, int > > que;
void dfs(int x, int y) {
(pair<int, int >(x, y));;
while (! ()) {
pair<int, int> t = ();
();
a[][] = 2;
for (int i = 0; i < 4; i++) {
// Search in all four directions
int nx = + d[i][0], ny = + d[i][1];
            // Don't go out of bounds and make sure the point is not searched, it feels like accessing the array would be slower, so it's placed afterward
if ( nx >= 0 && nx <= n + 1 && ny >= 0 && ny <= n + 1 && a[nx][ny] == 0 &&) {
(pair<int, int>(nx, ny));)
}
}
}
}

int main() {
cin >> n; for (int i = 1; i <= n; i++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
// Start searching from the outer attachment boundary
dfs(0, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << 2 - a[i][j]<<' '; //this space Hey~~!
}
//Don't forget to wrap each line with a newline.
cout << endl.
}
return 0; }
}