（1）迷宫
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗n 的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。

同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。

如果起点或者终点有一个不能通行(为#)，则看成无法办到。

注意：A、B不一定是两个不同的点。

输入格式
第1行是测试数据的组数 k，后面跟着 k 组输入。

每组测试数据的第1行是一个正整数 n，表示迷宫的规模是 n∗n 的。

接下来是一个 n∗n 的矩阵，矩阵中的元素为.或者#。

再接下来一行是 4 个整数 ha,la,hb,lb，描述 A 处在第 ha 行, 第 la 列，B 处在第 hb 行, 第 lb 列。

注意到 ha,la,hb,lb 全部是从 0 开始计数的。

输出格式
k行，每行输出对应一个输入。

能办到则输出“YES”，否则输出“NO”。

数据范围
1≤n≤100
输入样例：
2
3
.##
..#

..

0 0 2 2
5
.....

.

..#..

..

…#.
0 0 4 0
输出样例:
YES
NO

代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
char g[N][N];
int xa, ya, xb, yb;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool st[N][N];

bool dfs(int x, int y)
{
    if (g[x][y] == '#') return false;
    if (x == xb && y == yb) return true;

    st[x][y] = true;

    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= n) continue;
        if (st[a][b]) continue;
        if (dfs(a, b)) return true;
    }

    return false;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
        scanf("%d%d%d%d", &xa, &ya, &xb, &yb);

        memset(st, 0, sizeof st);
        if (dfs(xa, ya)) puts("YES");
        else puts("NO");
    }

    return 0;
}

总结：因为是内部搜索，一个状态向另外一个状态拓展的时候，这个状态是不会变化的。每个状态只搜索一次，所以不需要回溯，因为st[x][y]标记当前点(x,y)被搜索到,当你恢复现场的时候,假设你是从(px,py)搜到点(x,y)的时候,你在判断(x,y)可以被(px,py)到达之后已经将(x,y)计数一次,当你下次再从某个(px2,py2)搜到(x,y)的时候,此时要通过st[x][y]判重,如果你恢复现场,那么你将再从将(x,y)进行搜索,所以不要恢复现场

(2)红与黑
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式
输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖；
2）‘#’：红色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

输出格式
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围
1≤W,H≤20
输入样例：
6 9
....#.
.....#
......
......
......
......
......

@…#

.#..#.
0 0
输出样例：
45
代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25;

int n, m;
char g[N][N];
bool st[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs(int x, int y)
{
    int cnt = 1;

    st[x][y] = true;
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (g[a][b] != '.') continue;
        if (st[a][b]) continue;

        cnt += dfs(a, b);
    }

    return cnt;
}

int main()
{
    while (cin >> m >> n, n || m)
    {
        for (int i = 0; i < n; i ++ ) cin >> g[i];

        int x, y;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == '@')
                {
                    x = i;
                    y = j;
                }

        memset(st, 0, sizeof st);
        cout << dfs(x, y) << endl;
    }

    return 0;
}


#include <iostream>
#include <queue>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 25;

int n, m;
char g[N][N];

int bfs(int sx, int sy)
{
    queue<PII> q;
    q.push({sx, sy});
    g[sx][sy] = '#';
    int res = 0;

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        res ++ ;

        for (int i = 0; i < 4; i ++ )
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue;
            g[x][y] = '#';
            q.push({x, y});
        }
    }
    return res;
}

int main()
{
    while (cin >> m >> n, n || m)
    {
        for (int i = 0; i < n; i ++ ) cin >> g[i];
        int x, y;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == '@')
                {
                    x = i;
                    y = j;
                }
        cout << bfs(x, y) << endl;
    }

    return 0;
}

(3) 马走日
马在中国象棋以日字形规则移动。

请编写一段程序，给定 n∗m 大小的棋盘，以及马的初始位置 (x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

输入格式
第一行为整数 T，表示测试数据组数。

每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标 n,m,x,y。

输出格式
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，若无法遍历棋盘上的所有点则输出 0。

数据范围
1≤T≤9,
1≤m,n≤9,
0≤x≤n−1,
0≤y≤m−1
输入样例：
1
5 4 0 0
输出样例：
32
代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;

int n, m;
bool st[N][N];
int ans;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void dfs(int x, int y, int cnt)
{
    if (cnt == n * m)   //如果所有的点都搜完了，搜到最后一个点了，说明是个合法方案，return
    {
        ans ++ ;
        return;
    }
    st[x][y] = true;

    for (int i = 0; i < 8; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (st[a][b]) continue;
        dfs(a, b, cnt + 1);
    }

    st[x][y] = false;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        int x, y;
        scanf("%d%d%d%d", &n, &m, &x, &y);

        memset(st, 0, sizeof st);
        ans = 0;
        dfs(x, y, 1);   //当前点正在第一个点

        printf("%d\n", ans);
    }

    return 0;
}

(4)单词接龙
单词接龙是一个与我们经常玩的成语接龙相类似的游戏。

现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”，每个单词最多被使用两次。

在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish ，如果接成一条龙则变为 beastonish。

我们可以任意选择重合部分的长度，但其长度必须大于等于1，且严格小于两个串的长度，例如 at 和 atide 间不能相连。

输入格式
输入的第一行为一个单独的整数 n 表示单词数，以下 n 行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示“龙”开头的字母。

你可以假定以此字母开头的“龙”一定存在。

输出格式
只需输出以此字母开头的最长的“龙”的长度。

数据范围
n≤20
输入样例：
5
at
touch
cheat
choose
tact
a
输出样例：
23
提示
连成的“龙”为 atoucheatactactouchoose。
代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 22;
int g[N][N]; //存的第i个单词的后缀与第j个单词的前缀相同的单词个数
int used[N];
int ans;
string word[N];
int n;

int dfs(string dragon,int last)
{
    ans = max((int)dragon.size(), ans);
    used[last]++;

    for(int i=0;i<n;i++)
    {
        if(g[last][i]&&used[i]<2)
        {
            dfs(dragon + word[i].substr(g[last][i]), i);
        }
    }

    used[last]--;

    return ans;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>word[i];
    char start;
    cin>>start;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            string a=word[i];
            string b=word[j];
            for(int k=1;k<min(a.size(),b.size());k++)
            {
                if(a.substr(a.size()-k,k)==b.substr(0,k))
                {
                    g[i][j]=k;
                    break;      //前缀和后缀相同字母越短越好，连起来的字符串越长
                }
            }
        }
    }
    for (int i = 0; i < n; i ++ )
        if (word[i][0] == start)
            dfs(word[i], i);

    cout << ans << endl;

}

（5）分成互质组
给定 n 个正整数，将它们分组，使得每组中任意两个数互质。

至少要分成多少个组？

输入格式
第一行是一个正整数 n。

第二行是 n 个不大于10000的正整数。

输出格式
一个正整数，即最少需要的组数。

数据范围
1≤n≤10
输入样例：
6
14 20 33 117 143 175
输出样例：
3
代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 15;
vector<int> g[N];
int nums[N];
int ans = N;
int n;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

bool check(vector<int>& vec, int x)
{
    for (int i = 0; i < vec.size(); i++)
        if (gcd(vec[i], x) > 1) return false;
    return true;
}

// u是当前处理到序列的下标，used是目前使用到的组数
void dfs(int u, int used)
{
    // 剪枝：如果当前使用的组已经>=目前获得的最优解，停止当前分支的搜索
    if (used +1 >= ans) return;
    if (u >= n)
    {
        // ans = min(ans, used + 1);
        ans=used+1;
    }
    // 先在已经使用的组里面找，看看能不能插进去
    for (int i = 0; i <= used; i++)
    {
        if (check(g[i], nums[u]))
        {
            g[i].push_back(nums[u]);
            dfs(u + 1, used);
            g[i].pop_back();
        }
    }
    // 剪枝：因为n个数最多只放进n个组，所以只要总组数<=n，允许尝试放进新的组
    if (used + 1 <= n)
    {
        g[used + 1].push_back(nums[u]);
        dfs(u + 1, used + 1);
        g[used + 1].pop_back();
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &nums[i]);
    // 初始处理nums[0], 初始放入g[0]
    dfs(0, 0);
    printf("%d\n", ans);
    return 0;
}

(6)小猫爬山
翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。

经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。

当然，每辆缆车上的小猫的重量之和不能超过 W。

每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？

输入格式
第 1 行：包含两个用空格隔开的整数，N 和 W。

第 2..N+1 行：每行一个整数，其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。

输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。

数据范围
1≤N≤18,
1≤Ci≤W≤108
输入样例：
5 1996
1
2
1994
12
29
输出样例：
2
代码

//第一个参数：第几个数了到  第二个参数：第几组
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

int n, m;
int w[N];
int sum[N];
int ans = N;

void dfs(int u, int k)
{
    // 最优性剪枝
    if (k >= ans) return;
    if (u == n)
    {
        ans = k;
        return;
    }

    for (int i = 0; i < k; i ++ )
        if (sum[i] + w[u] <= m) // 可行性剪枝
        {
            sum[i] += w[u];
            dfs(u + 1, k);
            sum[i] -= w[u]; // 恢复现场
        }

    // 新开一辆车
    sum[k] = w[u];
    dfs(u + 1, k + 1);
    sum[k] = 0; // 恢复现场
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> w[i];

    // 优化搜索顺序
    sort(w, w + n);
    reverse(w, w + n);

    dfs(0, 0);

    cout << ans << endl;

    return 0;
}

(7)石油采集
链接：https://ac.nowcoder.com/acm/problem/15107
来源：牛客网

随着海上运输石油泄漏的问题，一个新的有利可图的行业正在诞生，那就是撇油行业。如今，在墨西哥湾漂浮的大量石油，吸引了许多商人的目光。这些商人们有一种特殊的飞机，可以一瓢略过整个海面20米乘10米这么大的长方形。（上下相邻或者左右相邻的格子，不能斜着来）当然，这要求一瓢撇过去的全部是油，如果一瓢里面有油有水的话，那就毫无意义了，资源完全无法利用。现在，商人想要知道，在这片区域中，他可以最多得到多少瓢油。

地图是一个N×N的网络，每个格子表示10m×10m的正方形区域，每个区域都被标示上了是油还是水
输入描述:
测试输入包含多条测试数据
测试数据的第一行给出了测试数据的数目T（T<75）
每个测试样例都用数字N（N<50）来表示地图区域的大小，接下来N行，每行都有N个字符，其中符号’.’表示海面、符号’#’表示油面。
输出描述:
输出格式如下“Case X: M”（X从1开始），M是商人可以最多得到的油量。
示例1
输入
复制
1
6
......
.##…
......
.#..#.
.#..##
......
输出
复制
Case 1: 3
代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 55;
char graph[maxn][maxn];
int T,n,odd,even;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,1,-1};

void dfs(int x,int y){
    int nx,ny;
    if((x+y)&1) odd ++;
    else even ++;
    graph[x][y] = '.';
    for (int i = 0;i < 4;i ++){
        nx = x + dx[i];
        ny = y + dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n || graph[nx][ny] == '.') continue;
        dfs(nx,ny);
    }
}

int main(){
    cin >> T;
    for (int kcase = 1;kcase <= T;kcase ++){
        cin >> n;
        for (int i = 0;i < n;i ++){
            scanf("%s",graph[i]);
        }
        int ans = 0;
        for (int i = 0;i < n;i ++){
            for (int j = 0;j < n;j ++){
                if (graph[i][j] == '#'){
                    odd = even = 0;
                    dfs(i,j);
                    ans += min(odd,even);
                }
            }
        }
        cout << "Case "<<kcase <<": " << ans << endl;
    }
    return 0;
}