D - red and black
The garlic factory has a rectangular house with square tiles of red and black on the ground. You stand on one of the black tiles and can only move to the adjacent black tiles. Please write a program to calculate how many black tiles you can reach.
Idea: use dfs to search. At the same time, the rows and columns are no more than 20, and there will be no timeout. Pay attention to the conditions given in the title: you stand on one of the black tiles.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int w, h, ax, ay, ans = 1;
string mp[25];
int v[25][25];
int dir[4][2] = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
bool in( int x, int y ){
if( x > -1 && x < h && y > -1 && y < w)
return true;
else
return false;
}//Judge whether it is within the legal scope
void dfs( int x, int y){
for( int i = 0; i <4; i++ ){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if( in( xx, yy ) && mp[xx][yy] == '.' && !v[xx][yy] ){
v[xx][yy] = 1;
++ans;
dfs( xx, yy );//Note that backtracking is not required, otherwise it will be a dead cycle
}
}
}
int main()
{
ios :: sync_with_stdio( false );
cin.tie( NULL );
cin >> w >> h;
int flag = 1;
for( int i = 0; i < h; i++ ){
cin >> mp[i];
for( int j = 0; j < w && flag; j++ ){
if( mp[i][j] == '@' ){
ax = i;
ay = j;
flag = 0;
}//Record target location
}
}
dfs( ax, ay );
cout << ans << endl;
return 0;
}E - MA Zori
The horse moves in the shape of a Japanese character in Chinese chess. Please write a program, given n × mn × m-Size chessboard and the initial position (x,y)(x,y) of the horse are required not to repeatedly pass through the same point on the chessboard. Calculate how many ways the horse can traverse all points on the chessboard.
Idea: dfs, note that the end condition is that all points have been passed. 1. Note that the initial position should also be marked. 2. Note that when judging in, we should find out what x and y are less than or equal to or greater. 3. When writing dfs functions, you should pay attention to the end conditions, whether to backtrack, and the parameters passed by dfs.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int x, y, m, n, t, ans;
int v[15][15];
int dir[8][2] = {
{ -1, -2 }, { 1, -2 }, { -2, -1 }, { 2, -1 },
{ -2, 1 }, { 2, 1 }, { -1, 2 }, { 1, 2 }
};//Check more when writing
bool in( int x, int y ){
if( x > -1 && x < n && y > -1 && y < m )
return true;
else
return false;
}
void dfs( int x, int y, int cnt ){
if( cnt == n * m ){
++ans;
return ;
}
for( int i = 0; i < 8; i++ ){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if( in( xx, yy ) && !v[xx][yy] ){
v[xx][yy] = 1;
dfs( xx, yy, cnt + 1 );
v[xx][yy] = 0;
}
}
}
int main()
{
ios :: sync_with_stdio( false );
cin.tie( NULL );
cin >> t;
while( t-- ){
cin >> n >> m >> x >> y;
memset( v, 0, sizeof( v ) );//Note that when there are multiple sets of samples, remember to empty something.
ans = 0;
v[x][y] = 1;
dfs( x, y, 1 );
cout << ans << endl;
}
return 0;
}G - N Queens
It's the n queen problem.
Idea: add row by row, but judge whether it can be added in this column when adding. Judge the positive and negative slope of the column. It can be deduced from the mathematical formula here that the positive slope is r (row) + l (column), and the inverse slope is j (y) - r (x). However, the inverse slope indicates that there is likely to be a negative number, so we use n - (j - r), but this means that the slope array should be twice as large. Because we are not sure whether this strategy is right, we need to go back. The end condition is: it is arranged to the last line.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, k1[25], k2[25], hav[15];
string mp[15];
void dfs( int r ){
if( r == n ){//Because if you can arrange this line, you can place it
for( int i = 0; i < n; i++ ){
for( int j = 0; j < n; j++ ){
cout << mp[i][j];
}
cout << endl;
}
cout << endl;
return ;
}
for( int j = 0; j < n; j++ ){
if( !hav[j] && !k1[j + r] && !k2[r - j + n] ){
//If this column has not been used, and the forward and backward slashes meet the conditions
mp[r][j] = 'Q';
k1[j + r] = 1;
k2[ n - ( j - r )] = 1;
hav[j] = 1;
dfs( r + 1 );
//to flash back
mp[r][j] = '.';
k1[j + r] = 0;
k2[n - ( j - r )] = 0;
hav[j] = 0;
}
}
}
int main()
{
ios :: sync_with_stdio( false );
cin.tie( NULL );
cin >> n;
for( int i = 0; i < n; i++ ){
for( int j = 0; j < n; j++ ){
mp[i][j] = '.';
}
}
//Build chessboard
/*Note that it is better not to directly assign a string with = because string is equivalent to a container and string mp is just a declaration,
In essence, there is no memory. If you assign this value, it will overflow, which is equivalent to vector, but the compiler will generally help you automatically.
It can be changed to:
for( int i = 0; i < n; i++ ){
for( int j = 0; j < n; j++ ){
mp[i] += '.';
}
}
*/
dfs( 0 );
return 0;
}A - Prime Ring Problem
Give a number num, arrange the num number of 1-num, so that the ring composed of this sequence satisfies that the sum of any two adjacent additions is prime, and the first of all sequences is 1, so as to output all sequences that meet the conditions.
Idea: dfs, but this is the state dfs, and the final number should be judged with 1. Note that the format of this question is very strict. You can't output redundant spaces and presentation errors. The end condition is that the length of the sequence meets the requirements. Obviously, this problem needs to be traced back. The parameter passed by dfs is the number at the current position (to facilitate the comparison with the following numbers, check whether it is a prime number and the length of the current sequence, so as to facilitate the judgment of the end condition)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int mp[20], v[20], show[20];
int num;
bool isPrime( int num )
{
if( num == 2 || num == 3 ) //Two smaller decimals are treated separately
return 1 ;
if( num % 6 != 1 && num % 6 != 5 ) //What is not on either side of a multiple of 6 must not be a prime number
return 0 ;
int tmp = sqrt( num );
for( int i = 5; i <= tmp; i += 6 ) //On either side of a multiple of 6 may not be prime
if( num % i == 0 || num % ( i + 2) == 0 ) //Excluding all, the rest is prime
return 0 ;
return 1 ;
} //A board for judging whether it is a prime number or not
void dfs( int now, int cnt ){
if( cnt == num ){
int y = 1;
for( int i = 0; i < num; i++ ){
if( y == 1 ){
cout << show[i];
}
else{
cout << " " << show[i];
}
++y;
}
cout << endl;
}
for( int i = 2; i <= num; i++ ){
if( isPrime( now + i ) && !v[i] ){
v[i] = 1;
if( cnt == num - 1 && isPrime( i + 1 ) ){//Note that special judgment shall be made for the last number
show[ cnt ] = i;
dfs( i, cnt + 1 );
}
else if( cnt != num - 1 ){
show[ cnt ] = i;
dfs( i, cnt + 1 );
}
v[i] = 0;
}
}
}
int main()
{
ios :: sync_with_stdio( false );
cin.tie( NULL );
int t = 1;
while( cin >> num ){
memset( v, 0, sizeof( v ) );
if( t == 1 ){
cout << "Case " << t << ":\n";
}
else{
cout << "\nCase " << t << ":\n";
}
++t;
v[1] = 1;//Note that the starting point must be marked, otherwise it will be marked
show[0] = 1;//Use the show array to record the number on the sequence
dfs( 1, 1 );
}
return 0;
}Prime board 1
bool isPrime( int num )
{
if( num == 2 || num == 3 ) //Two smaller decimals are treated separately
return 1 ;
if( num % 6 != 1 && num % 6 != 5 ) //What is not on either side of a multiple of 6 must not be a prime number
return 0 ;
int tmp = sqrt( num );
for( int i = 5; i <= tmp; i += 6 ) //On either side of a multiple of 6 may not be prime
if( num % i == 0 || num % ( i + 2) == 0 ) //Excluding all, the rest is prime
return 0 ;
return 1 ;
} F - Sticks
Given the length of n (max = 64) small sticks (max = 50), ask how to combine (one group or multiple groups) so that the sum of each group is the same and the sum is the smallest.
Idea: (if the position of the sequence is not changeable, I feel that the dichotomy of this problem can also be done... Because it is changeable, dfs is adopted). In order to reduce the branches as much as possible, it is obvious that the maximum length is the sum of the lengths of the small sticks, and the minimum is the length of the largest sticks. Moreover, this length must be divisible by the total length. At the same time, as long as the length is traversed from small to large, it must be the smallest length. Obviously, this problem needs to be traced back. At the same time, the main dfs parameters are how much is left in the current one, how much is left in the total, and there are a lot of end conditions. 1. If sum is 0 and there is no left in the one being done, then end it. 2. If the current one is finished, set rlen to len. 3. If rlen > sum, it indicates that it is not enough, It means that this length is wrong. And the if in the for loop is also very good. This problem is also very good—— If the wooden sticks are sorted in advance, and the current wooden stick = = rlen, there is no need to compare the later wooden sticks of the same length; If this length of stick is just right rlen, then the back is not right; If rlen is equal to len and the dfs in front has been judged, there is no wooden stick in at this time, which means that it can't match in the future. It's too classic to reduce branches!!! Anyway, it's all kinds of subtraction!!!
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n, mp[100], v[100], sum, ans;
int dfs( int len, int rlen, int sum ){
if( !rlen && !sum )
return len;
if( !rlen )
rlen = len;
if( rlen > sum )
return 0;
for( int i = 0; i < n; i++ ){
if( rlen >= mp[i] && !v[i] ){
v[i] = 1;
if( dfs( len, rlen - mp[i], sum - mp[i] ) )
return len;
v[i] = 0;
if( rlen == len || mp[i] >= rlen )
break;
while( mp[i] == rlen )
++i;
}
}
return 0;
}
bool cmp( int a, int b ){
return a > b;
}
int main()
{
ios :: sync_with_stdio( false );
cin.tie( NULL );
while( cin >> n && n != 0 ){
sum = 0;
for( int i = 0; i < n; i++ ){
cin >> mp[i];
sum += mp[i];
}
sort( mp, mp + n, cmp );
for( int i = mp[0]; i <= sum; i++ ){
memset( v, 0, sizeof( v ) );
if( sum % i == 0 ){
ans = dfs( i, i, sum );
if( ans ){
cout << ans << endl;
break;
}
}
}
}
return 0;
}Summary:
After doing these questions, I found some conventional routines of dfs. When writing dfs, you should pay attention to the marking of the start point, the parameters passed by dfs, how to judge the end condition, and whether backtracking is required. In addition, when you encounter a timeout problem, you should see whether pruning is required. Moreover, you should be careful when writing dfs. Generally, the code of dfs is relatively long. You should pay attention to the wrong typing.