Flip Game(poj1753)

Original question link
Topic type: Enumeration
At the beginning, I was very confused to see this problem. Since the turning of one point will affect the other points next to me, the problems such as which point to turn, how to enumerate, and how to determine whether it is necessary to turn poured into my mind. After thinking about it for a long time, I couldn't find a positive solution.
Further analysis, I found that I had forgotten the essence of enumeration. Trying to find a solution to determine whether this point needs to be flipped is absurd in the topic of enumeration type, so this problem is pass ed.
The point from which to start flipping directly determines the order of enumeration, and the problem of which point to start flipping fundamentally determines that the flipping order of points will have an impact on the final result. This is because intuitively, the last flipping will affect the color of chess pieces, but we can only check the color of chess pieces at the end, This problem is solved by transforming the intermediate process into the number of flips and acting on the original matrix.
Thus, you only need to enumerate 16 cases of point turning or no turning 2 ^ 16.
It should be noted that pruning can be performed properly during enumeration.

#include<iostream>
using namespace std;
int A[4][4], B[4][4], C[4][4];
int res = 17;

int main() {
	char c;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			c = getchar();
			if (c == 'b') A[i][j] = 1;
			else A[i][j] = 0;
		}
		getchar();
	}
	
	for (int a = 0; a < 16; a++) {
		int c1 = 0;
		B[0][3] = a % 2, B[0][2] = (a >> 1) % 2, B[0][1] = (a >> 2) % 2, B[0][0] = (a >> 3) % 2;
		if (B[0][3]) c1++; if (B[0][2]) c1++; if (B[0][1]) c1++; if (B[0][0]) c1++;

		for (int b = 0; b < 16; b++) {
			int c2 = 0;
			B[1][3] = b % 2, B[1][2] = (b >> 1) % 2, B[1][1] = (b >> 2) % 2, B[1][0] = (b >> 3) % 2;
			if (B[1][3]) c2++; if (B[1][2]) c2++; if (B[1][1]) c2++; if (B[1][0]) c2++;

			for (int c = 0; c < 15; c++) {
				int c3 = 0;
				B[2][3] = c % 2, B[2][2] = (c >> 1) % 2, B[2][1] = (c >> 2) % 2, B[2][0] = (c >> 3) % 2;
				if (B[2][3]) c3++; if (B[2][2]) c3++; if (B[2][1]) c3++; if (B[2][0]) c3++;

				for (int d = 0; d < 15; d++) {
					int c4 = 0;
					B[3][3] = d % 2, B[3][2] = (d >> 1) % 2, B[3][1] = (d >> 2) % 2, B[3][0] = (d >> 3) % 2;
					if (B[3][3]) c4++; if (B[3][2]) c4++; if (B[3][1]) c4++; if (B[3][0]) c4++;
					//cout << c1+c2+c3+c4 << endl;
					/*if (c1 + c2 + c3 + c4 <= 4) {
						printf("hi");
					}*/
					//Ca matrix C
					if (c1 + c2 + c3 + c4 >= res) continue;//prune
					int index0 = 0, index1 = 0;
					memcpy(C, A, sizeof(A));
					for (int i = 0; i < 4; i++) {
						for (int j = 0; j < 4; j++) {
							if (B[i][j]) {
								C[i][j] ++;
								if (i - 1 >= 0) C[i - 1][j]++;
								if (j - 1 >= 0) C[i][j - 1]++;
								if (i + 1 < 4) C[i + 1][j]++;
								if (j + 1 < 4) C[i][j + 1]++;
							}
						}
					}
					//verify matrix C
					for (int i = 0; i < 4; i++) {
						for (int j = 0; j < 4; j++) {
							if (C[i][j] %2 == 0 && !index0) index0 = 1; //when 0 first appear 
							if (C[i][j] %2 == 1 && !index1) index1 = 1; //when 1 first appear
							if (index0 && index1) goto over;
						}
					}
					over:
					if (index1 && index0) continue; //both 0 and 1 appear
					else {
						if (c1 + c2 + c3 + c4 < res) res = c1 + c2 + c3 + c4;
					}
				}
			}
		}
	}
	if (res == 0) printf("0\n");
	else if (res == 17) printf("Impossible\n");
	else printf("%d\n", res);
} 

Changing Digits(poj3373)

Original question link
Topic type: dfs that specifies the search direction
About division

a/b, then a is the divisor and b is the divisor. If the remainder of a/b is 0, then b divides a or a can be divided by b

Reference problem solution

(forgive me for not being able to write. Here are some summaries after reading the explanation)

The first thing that comes to mind is how to store high-precision data and how to calculate.
Processing of high precision data
The solution to the high-precision problem returns to the original manual operation about addition, subtraction, multiplication and division, and writes the program according to the processing rules. Addition and subtraction are each operation, and then deal with the problem of carry and borrow. Multiplication is transformed into addition and division into subtraction, which is consistent with the content learned in the course of principles of computer composition.

This problem is solved, but it will be found that if the method described above is used in each operation, it may be too cumbersome. In the problem solution indicated above, a congruence table is given by using the property of congruence. Since the size of K is limited, the table contains n digits * k elements.

We all know that DFS is an exhaustive and violent method. At that time, we thought this method was not feasible because there were too many exhaustive solutions. How to record when multiple solutions meet the conditions, so as to facilitate subsequent comparison and output of results. However, I ignore the influence of exhaustive direction on the problem solving rate. When we specify the direction of exhaustion, the first solution is the correct solution.

The next step is about the direction of DFS, which has been described in detail in the reference link, so I won't repeat it.

Summary:

It's Friday.