所谓暴力法，是把所有可能的情况都罗列出来，然后逐一检查，从中找到答案。
暴力法往往是“低效”的代名词。不过相对其他“高效”算法，暴力法不仅简单且编码量一般都更短更好写。所以当拿到一个题目后，首先想想如何用暴力法解决。如果暴力法的代码能满足题目要求的时间和空间限制，就用暴力法。若暴力法不能满足要求，也可以把它当成对照，用来验证高级算法的正确性。
暴力搜索的思路很简单，但是有的时候操作起来并不容易。比如蓝桥杯中常见的迷宫问题：
深度优先搜索（DFS, Depth-First Search）和宽度优先搜索（BFS, Breadth-First Search，或称为广度优先搜索）是基本的暴力技术，常用于解决图、树的遍历问题。
以老鼠走迷宫为例说明 BFS 和 DFS 的原理。迷宫内的路错综复杂，老鼠从入口进去后，怎么才能找到出口。有两种方案：
具体编程时，一般用队列这种数据结构来实现 BFS ，即 “BFS = 队列”；
而 DFS 一般用递归实现，即 “DFS = 递归”。
设数字是 {1 2 3 4 5......n}，那么递归求全排列
让第一个数不同，得到 n 个数列。其办法是：把第 1 个和后面每个数交换。
以上 n 个数列，只要第一个数不同，不管后面 n−1 个数是怎么排列的，这 n 个数列都不同。 这是递归的第一层。
继续：在上面的每个数列中，去掉第一个数，对后面的 n−1 个数进行类似的排列。例如从上面第 2 行的{2 1 3 4 5......n}进入第二层（去掉首位 2）：
以上 n-1 个数列，只要第一个数不同，不管后面 n-2 个数是怎么排列的，这 n-1 个数列都不同。
这是递归的第二层。
重复以上步骤，直到用完所有数字
import java.util.Scanner;
public class Main {
public static int[] a = new int[3];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
for (int i = 0; i <= 2; i++) {
a[i] = scanner.nextInt();
}
dfs(0, 2);
}
public static void dfs(int s, int t) {//从第s到第t的全排列
if (s == t) {//可以在这里控制数列长度（如果需要打印 nn 个数中任意 mm 个数的排列，例如在 44 个数中取任意 33 个数的排列）
for (int i = 0; i <= 2; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
return;
}
for (int i = s; i <= t; i++) {
swap(s, i);
dfs(s + 1, t);
swap(i, s);
}
}
public static void swap(int i, int j) {
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}以上不能按从小到大的顺序打印排列
C++ 纯暴力
#include<bits/stdc++.h>
using namespace std;
const int n=10;
char mp[n+2][n+2]; //用矩阵mp[][]存迷宫图。把静态数组定义在全局
bool vis[n+2][n+2]; //判断点是否曾走过，是“记忆化”功能
int ans = 0;
int cnt = 0;
bool dfs(int i, int j){
if (i<0 || i>n-1 || j<0 || j>n-1) return true; //走出了迷宫，停止
if (vis[i][j]) return false; //如果已经搜过，说明兜圈子了，走不出去
cnt++; //统计dfs()了多少次
vis[i][j] = true; //标记已搜索
if (mp[i][j] == 'L') return dfs(i, j - 1); //往左，继续dfs
if (mp[i][j] == 'R') return dfs(i, j + 1); //往右
if (mp[i][j] == 'U') return dfs(i - 1, j); //往上
if (mp[i][j] == 'D') return dfs(i + 1, j); //往下
}
int main(){
//本题是填空题，直接输出答案：
// cout << 31; return 0;
//如果不是填空，就写下面的代码：
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> mp[i][j]; //读取迷宫图
for (int i = 0; i < n; i++) //对每个点，判断是否能走出去
for (int j = 0; j < n; j++){
memset(vis, 0, sizeof(vis)); //搜索每个点前，都清空vis[]
if(dfs(i, j)) ans++; //点mp[i][j]能走出去，统计答案
}
cout <<"ans="<< ans <<", cnt="<<cnt<< endl; //输出答案
return 0;
}true，代码是第 99 行。false，代码是第 1010 行。什么情况下走不出迷宫？必然是兜圈子，回到了曾经走过的点。用 vis[i][j]vis[i][j] 记录点 (i, j)(i,j) 是否曾经走过，如果走过，就是兜圈子了。在做每个竞赛题时，都应该分析复杂度，看代码是否能在限定的时间和空间内完成。如果迷宫有 n 行 n 列，做一次 dfs()，那么最多需要走遍所有的点，即 O(n^2) 次。代码的 25−29 行对 n^2 个点，每个点都做了一次 dfs()，所以总复杂度是 O(n^4) 的。
#include<bits/stdc++.h>
using namespace std;
const int n=10;
char mp[n+2][n+2];
bool vis[n+2][n+2];
int solve[n+2][n+2]; //solve[i][j]=1表示这个点能走出去；=2表示出不去
int ans = 0;
int cnt = 0;
bool dfs(int i, int j){
if (i<0 || i>n-1 || j<0 || j>n-1) return true;
if(solve[i][j]==1) return true; //点(i,j)已经算过了，能出去
if(solve[i][j]==2) return false; //点(i,j)已经算过了，出不去
if (vis[i][j]) return false;
cnt++; //统计dfs()了多少次
vis[i][j] = true;
if (mp[i][j] == 'L'){
if(dfs(i, j - 1)){ solve[i][j] = 1;return true;}
//回退，记录整条路径都能走出去
else { solve[i][j] = 2;return false;}
//回退，记录整条路径都出不去
}
if (mp[i][j] == 'R') {
if(dfs(i, j + 1)){ solve[i][j] = 1;return true;}
else { solve[i][j] = 2;return false;}
}
if (mp[i][j] == 'U') {
if(dfs(i - 1, j)){ solve[i][j] = 1;return true;}
else { solve[i][j] = 2;return false;}
}
if (mp[i][j] == 'D') {
if(dfs(i + 1, j)){ solve[i][j] = 1;return true;}
else { solve[i][j] = 2;return false;}
}
}
int main(){
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> mp[i][j];
memset(solve, 0, sizeof(solve));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++){
memset(vis, 0, sizeof(vis));
if(dfs(i, j)) ans++;
}
cout <<"ans="<< ans <<",cnt="<<cnt<< endl;
return 0;
}上面是优化后的代码，代码中我用 solve[][] 完成了标记整个路径>这一工作：
public class Main {
private static boolean[][] visited = new boolean[7][7];
private static int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private static int count = 0;
public static void main(String[] args) {
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
visited[i][j] = false;
}
}
visited[3][3] = true;
dfs(3, 3);
System.out.println(count / 4);
}
public static void dfs(int x, int y) {
if (x == 0 || x == 6 || y == 0 || y == 6) {
count++;
return;
}
visited[x][y] = true;
visited[6 - x][6 - y] = true;
for (int i = 0; i < 4; i++) {
int x1 = x + direction[i][0];
int y1 = y + direction[i][1];
if (x1 < 0 || x1 > 6 || y1 < 0 || y1 > 6) {
continue;
}
if (visited[x1][y1]!=true) {
dfs(x1, y1);
}
}
visited[x][y] = false;
visited[6 - x][6 - y] = false;
}
}
样例输入
((xx|xxx)x|(x|xx))xx
样例输出
6import java.util.Scanner;
public class Main {
private static String string;
private static int len;
private static int point = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
string = scanner.next();
len = string.length();
System.out.println(dfs(string));
}
private static int dfs(String s) {
int tempLen = 0;
int ans = 0;
while (point < len) {
if (s.charAt(point) == '(') {
point++;
tempLen = tempLen + dfs(string);
} else if (s.charAt(point) == ')') {
point++;
return Math.max(ans,tempLen);
} else if (s.charAt(point) == 'x') {
point++;
tempLen++;
} else {
point++;
ans = tempLen;
tempLen = 0;
}
}
return Math.max(ans,tempLen);
}
}题目描述
现在小学的数学题目也不是那么好玩的。 看看这个寒假作业：
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
每个方块代表 1~13 中的某一个数字，但不能重复。
比如：
6 + 7 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
以及：
7 + 6 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？
public class Main {
private static int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
private static int ans = 0;
public static void main(String[] args) {
dfs(0, 12);
System.out.println(ans);
}
public static void dfs(int s, int t) {//剪枝
if (s == 3) {
if (!(a[0] + a[1] == a[2])) {
return;
}
}
if (s == 6) {
if (!(a[3] - a[4] == a[5])) {
return;
}
}
if (s == 9) {
if (!(a[6] * a[7] == a[8])) {
return;
}
}
if (s == 12) {
if(a[9]*a[10]==a[11]){
ans++;
}
}
for (int i = s; i <= t; i++) {
swap(i, s);
dfs(s + 1, t);
swap(s, i);
}
}
public static void swap(int i, int j) {
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}64种