首页 > 代码库 > dfs学习
dfs学习
棋盘问题
Input
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
Sample Input
2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1
Sample Output
2 1
题意：在给定的可放棋区域放K个棋，最多有多少中方法，限制是任意两个棋不能在同行或同列。
和八皇后差不多，代码：
#include <iostream> #include <cstring> #include <cstdio> using namespace std; int n, k, ans, res; char v[10][10]; int a[10]; void dfs(int x){ if(res == k){ ans++; return; } if(x >= n) return; for(int i = 0; i < n; i ++){ if(!a[i] && v[x][i] == ‘#‘){ a[i] = 1; res ++; dfs(x+1); res--; a[i] = 0; } } dfs(x+1); } int main(){ while(~scanf("%d%d",&n,&k)){ if(n == -1 && k == -1)break; ans = res = 0; for(int i = 0; i < n; i ++) cin >> v[i]; dfs(0); cout << ans << endl; } }
LETTERS
Before the begging of the game there is a figure in the upper-left corner of the board (first row, first column). In every move, a player can move the figure to the one of the adjacent positions (up, down,left or right). Only constraint is that a figure cannot visit a position marked with the same letter twice.
The goal of the game is to play as many moves as possible.
Write a program that will calculate the maximal number of positions in the board the figure can visit in a single game.
Input
The following R lines contain S characters each. Each line represents one row in the board.
Output
Sample Input
3 6 HFDFFB AJHGDH DGAGEH
Sample Output
6
题意就是从第一行第一列开始走，看最多能走几步，只能四个方向（上，下，左，右）而且走过的字母不能在走了。
没什么好说的，见代码：
#include <iostream> #include <cstdio> using namespace std; int n, m, maxn, dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1}; char a[25][25]; bool vis[25][25], ap[30];//vis标记地图，ap标记字母 void dfs(int x, int y, int ans){ for(int i = 0; i < 4; i ++){ int nx = x + dx[i], ny = y + dy[i]; if(0 <= nx && nx < n && 0 <= ny && ny < m && vis[nx][ny] == false && ap[a[nx][ny]-‘A‘] == false){ vis[nx][ny] = true; ap[a[nx][ny]-‘A‘] = true; //cout << nx << ‘ ‘ << ny << ‘ ‘ << ans << endl; dfs(nx, ny, ans+1); vis[nx][ny] = false; ap[a[nx][ny]-‘A‘] = false; } else maxn = max(maxn, ans); } } int main(){ while(~scanf("%d%d",&n,&m)){ maxn = 1; for(int i = 0; i < n; i ++) cin >> a[i]; vis[0][0] = true; ap[a[0][0]-‘A‘] = true; dfs(0,0,1); cout << maxn << endl; } }
Red and Black
Write a program to count the number of black tiles which he can reach by repeating the moves described above.
Input
There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.
‘.‘ - a black tile
‘#‘ - a red tile
‘@‘ - a man on a black tile(appears exactly once in a data set)
The end of the input is indicated by a line consisting of two zeros.
Output
Sample Input
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 11 9 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ........... 11 6 ..#..#..#.. ..#..#..#.. ..#..#..### ..#..#..#@. ..#..#..#.. ..#..#..#.. 7 7 ..#.#.. ..#.#.. ###.### ...@... ###.### ..#.#.. ..#.#.. 0 0
Sample Output
45 59 6 13
题意：从@开始可以从‘.’上走，到不能从‘#’上走，求最多能走几步。
直接遍历，代码：
#include <iostream> #include <cstdio> using namespace std; int n, m, ans; char a[50][50]; int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1}; void dfs(int x, int y){ a[x][y] = ‘#‘; for(int i = 0; i < 4; i ++){ int nx = x + dx[i], ny = y + dy[i]; if(0 <= nx && nx < n && 0 <= ny && ny < m && a[nx][ny] == ‘.‘){ ans ++; dfs(nx,ny); } } } int main(){ while(~scanf("%d%d",&m,&n)&&m&&n){ ans = 1; for(int i = 0; i < n; i ++) cin >> a[i]; int nx, ny; for(int i = 0; i < n; i ++){ for(int j = 0; j < m; j ++){ if(a[i][j] == ‘@‘){ nx = i; ny = j; goto tt; } } } tt: ; dfs(nx, ny); cout << ans << endl; } }
Kalevitch and Chess
A famous Berland‘s painter Kalevitch likes to shock the public. One of his last obsessions is chess. For more than a thousand years people have been playing this old game on uninteresting, monotonous boards. Kalevitch decided to put an end to this tradition and to introduce a new attitude to chessboards.
As before, the chessboard is a square-checkered board with the squares arranged in a8?×?8 grid, each square is painted black or white. Kalevitch suggests that chessboards should be painted in the following manner: there should be chosen a horizontal or a vertical line of 8 squares (i.e. a row or a column), and painted black. Initially the whole chessboard is white, and it can be painted in the above described way one or more times. It is allowed to paint a square many times, but after the first time it does not change its colour any more and remains black. Kalevitch paints chessboards neatly, and it is impossible to judge by an individual square if it was painted with a vertical or a horizontal stroke.
Kalevitch hopes that such chessboards will gain popularity, and he will be commissioned to paint chessboards, which will help him ensure a comfortable old age. The clients will inform him what chessboard they want to have, and the painter will paint a white chessboard meeting the client‘s requirements.
It goes without saying that in such business one should economize on everything — for each commission he wants to know the minimum amount of strokes that he has to paint to fulfill the client‘s needs. You are asked to help Kalevitch with this task.
Input
The input file contains 8 lines, each of the lines contains 8 characters. The given matrix describes the client‘s requirements, W character stands for a white square, and B character — for a square painted black.
It is guaranteed that client‘s requirments can be fulfilled with a sequence of allowed strokes (vertical/column or horizontal/row).
Output
Output the only number — the minimum amount of rows and columns that Kalevitch has to paint on the white chessboard to meet the client‘s requirements.
Example
WWWBWWBW
BBBBBBBB
WWWBWWBW
WWWBWWBW
WWWBWWBW
WWWBWWBW
WWWBWWBW
WWWBWWBW
3
WWWWWWWW
BBBBBBBB
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
1
题意：在8*8图上，最少画几画，B是画的，W是没画的，可以画一行或者一列。
说是dfs，其实就是一道规律题，每输入一行，就求下B的数量，如果是8的话，就可以当成画了一行，不是8的话，就是话了多少列了，等8行都是8个时就要特判下。
#include <iostream> using namespace std; char a[10]; int main(){ int res = 0, ans = 0; for(int i = 0; i < 8; i ++){ cin >> a; int k = 0; for(int i = 0; i < 8; i ++){ if(a[i] == ‘B‘) k++; } //cout << k << endl; if(k == 8) ans ++; else res = k; } if(ans == 8) cout << ans << endl; else cout << ans + res << endl; return 0; }
President‘s Office
President of Berland has a very vast office-room, where, apart from him, work his subordinates. Each subordinate, as well as President himself, has his own desk of a unique colour. Each desk is rectangular, and its sides are parallel to the office walls. One day President decided to establish an assembly, of which all his deputies will be members. Unfortunately, he does not remember the exact amount of his deputies, but he remembers that the desk of each his deputy is adjacent to his own desk, that is to say, the two desks (President‘s and each deputy‘s) have a common side of a positive length.
The office-room plan can be viewed as a matrix with n rows and m columns. Each cell of this matrix is either empty, or contains a part of a desk. An uppercase Latin letter stands for each desk colour. The ?period? character (?.?) stands for an empty cell.
Input
The first line contains two separated by a space integer numbers n, m (1?≤?n,?m?≤?100) — the length and the width of the office-room, and c character — the President‘s desk colour. The following n lines contain m characters each — the office-room description. It is guaranteed that the colour of each desk is unique, and each desk represents a continuous subrectangle of the given matrix. All colours are marked by uppercase Latin letters.
Output
Print the only number — the amount of President‘s deputies.
Example
3 4 R
G.B.
.RR.
TTT.
2
3 3 Z
...
.H.
..Z
0
题意：在给定的n行m列中，求于c相邻的字母有多少。两个或两个以上相同的字母当成一个。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1}; int vis[30]; char a[110][110]; int n, m, ans = 0; char c; void dfs(int x, int y){ for(int i = 0; i < 4; i++){ int nx = x + dx[i], ny = y + dy[i]; if(0 <= nx && nx < n && 0 <= ny && ny < m && isalpha(a[nx][ny]) && a[nx][ny] != c && vis[a[nx][ny] - ‘A‘] == 0){ vis[a[nx][ny]-‘A‘] = 1; ans++; a[nx][ny] = ‘.‘; } } } int main(){ while(cin>>n>>m>>c){ memset(vis, 0, sizeof(vis)); ans = 0; for(int i = 0; i < n; i ++) cin >> a[i]; for(int i = 0; i < n; i ++){ for(int j = 0; j < m; j ++){ if(a[i][j] == c){ dfs(i, j); } } } cout << ans << endl; } }
dfs学习