递归 | 昔人已乘黄鹤去此地空余黄鹤楼

1五子棋

描述

NowCoder最近爱上了五子棋，现在给你一个棋局，请你帮忙判断其中有没有五子连珠（超过五颗也算）。

输入描述：
输入有多组数据，每组数据为一张20x20的棋盘。
其中黑子用“*”表示，白子用“+”表示，空白位置用“.”表示。

输出描述：
如果棋盘上存在五子连珠（无论哪种颜色的棋子），输入“Yes”，否则输出“No”。

思路：
判断一个点位上的四个方向是否有一个存在五子连珠(0,1) (1,0) (1,1) (1,-1)

解答

#include <iostream>
#include <vector>
using namespace std;
bool checkDirection(vector<string>& board, int x, int y, int dx, int dy) {
    char player = board[x][y];
    for (int i = 0; i < 5; i++) {
        int newX = x + i * dx;
        int newY = y + i * dy;
        if (newX < 0 || newX >= 20 || newY < 0 || newY >= 20 ||
                board[newX][newY] != player) {
            return false;
        }
    }
    return true;
}

bool hasFiveInARow(vector<string>& board) {
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            if (board[i][j] != '.') {
                if (checkDirection(board, i, j, 1, -1) ||
                        checkDirection(board, i, j, 0, 1) || checkDirection(board, i, j, 1, 1) ||
                        checkDirection(board, i, j, 1, 0)) {
                    return true;
                }
            }
        }
    }
    return false;
}

int main() {
    vector<string> board(20);
    while (cin >> board[0]) {
        for (int i = 1; i < 20; i++) {
            cin >> board[i];
        }

        if (hasFiveInARow(board)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

2kotori和迷宫

题目描述
kotori在一个n*m迷宫里，迷宫的最外层被岩浆淹没，无法涉足，迷宫内有k个出口。kotori只能上下左右四个方向移动。她想知道有多少出口是她能到达的，最近的出口离她有多远？

输入描述:

1
2
3

第一行为两个整数n和m，代表迷宫的行和列数 (1≤n,m≤30)
后面紧跟着n行长度为m的字符串来描述迷宫。'k'代表kotori开始的位置，
'.'代表道路，'*'代表墙壁，'e'代表出口。保证输入合法。

输出描述:

1
2
3

若有出口可以抵达，则输出2个整数，第一个代表kotori可选择的出口的数量，
第二个代表kotori到最近的出口的步数。（注意，kotori到达出口一定会离开迷宫）
若没有出口可以抵达，则输出-1。

思路：
出口不止一个，需要比较进行比较选择最优
BFS可以用来寻找最优方案

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 定义方向数组，表示上下左右四个方向的移动
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

struct Position {
    int x, y, step;
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> maze(n);
    queue<Position> q;
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    // 读取迷宫并找到kotori的起始位置
    for (int i = 0; i < n; ++i) {
        cin >> maze[i];
        for (int j = 0; j < m; ++j) {
            if (maze[i][j] == 'k') {
                q.push({i, j, 0});
                visited[i][j] = true;
            }
        }
    }

    int exit_count = 0;
    int min_distance = 0x3f;

    // BFS搜索
    while (!q.empty()) {
        Position cur = q.front();
        q.pop();

        // 检查是否到达出口
        if (maze[cur.x][cur.y] == 'e') {
            exit_count++;
            min_distance = min(min_distance, cur.step);
            continue;
        }

        // 扩展到四个方向
        for (int i = 0; i < 4; ++i) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            // 判断新位置是否在迷宫内，并且可以走
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && maze[nx][ny] != '*') {
                visited[nx][ny] = true;
                q.push({nx, ny, cur.step + 1});
            }
        }
    }

    // 输出结果
    if (exit_count > 0) {
        cout << exit_count << " " << min_distance << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

3走迷宫

描述
NowCoder最喜欢游乐场的迷宫游戏，他和小伙伴们比赛谁先走出迷宫。
现在把迷宫的地图给你，你能帮他算出最快走出迷宫需要多少步吗？

输入描述：
输入包含多组数据。
每组数据包含一个10*10，由“#”和“.”组成的迷宫。其中“#”代表墙；“.”代表通路。
入口在第一行第二列；出口在最后一行第九列。
从任意一个“.”点都能一步走到上下左右四个方向的“.”点。

输出描述：
对应每组数据，输出从入口到出口最短需要几步。

和上面的题目一样的思路BFS

解答

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct Position{
    int x,y,step;
};

int bfs(vector<string>& maze){
    vector<vector<bool>> visited(10,vector<bool>(10,false));
    queue<Position> q;

    q.push({0,1,0});
    visited[0][1]=true;
    while(!q.empty()){
        Position cur=q.front();
        q.pop();

        if(cur.x==9&&cur.y==8){
            return cur.step;
        }

        for(int k=0;k<4;k++){
            int newX=cur.x+dx[k];
            int newY=cur.y+dy[k];
            if(newX>=0&&newX<10&&newY>=0&&newY<10&&!visited[newX][newY]&&maze[newX][newY]!='#'){
                q.push({newX,newY,cur.step+1});
                visited[newX][newY]=true;
            }
        }
    }
    return -1;
}

int main() {
    vector<string> maze(10);

    while(cin>>maze[0]){
        for(int i=1;i<10;i++){
            cin>>maze[i];
        }

        cout<<bfs(maze)<<endl;
    }
    return 0;
}

描述
一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。
例如：如果袋子里面的球的号码是{1, 1, 2, 3}，这个袋子就是幸运的，因为1 + 1 + 2 + 3 > 1 * 1 * 2 * 3
你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)，要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。

输入描述：
第一行输入一个正整数n(n ≤ 1000) 第二行为n个数正整数xi(xi ≤ 1000)

输出描述：
输出可以产生的幸运的袋子数

思路：先排序

解答

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dfs(vector<int>& arr,int pos,int sum,int multi){
    int count=0;
    for(int i=pos;i<arr.size();i++){
        sum+=arr[i];
        multi*=arr[i];
        if(sum>multi){
            count+=1+dfs(arr,i+1,sum,multi);
        }else if(arr[i]==1){
            count+=dfs(arr,i+1,sum,multi);
        }else{
            break;
        }
        //回溯
        sum-=arr[i];
        multi/=arr[i];
        //去重
        while((i+1<arr.size())&&arr[i]==arr[i+1]) i++;
    }
    return count;
}
int main() {
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++) cin>>arr[i];
    sort(arr.begin(),arr.end());
    cout<<dfs(arr,0,0,1)<<endl;
    return 0;
}

5矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

class Solution {
    int m, n;
    int memo[201][201];
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size(), n = matrix[0].size();
        function<int(int, int)> dfs = [&](int x, int y) -> int {
            int ret = 1;//至少有一个数
            if (memo[x][y] != 0)
                return memo[x][y];
            for (int k = 0; k < 4; k++) {
                int newX = x + dx[k];
                int newY = y + dy[k];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n &&
                    matrix[x][y] < matrix[newX][newY]) {
                    ret = max(ret, dfs(newX, newY) + 1);
                }
            }
            memo[x][y] = ret;
            return ret;
        };
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = max(ans, dfs(i, j));
            }
        }
        return ans;
    }
};

6滑雪

描述

给定一个 n×m 的矩阵，矩阵中的数字表示滑雪场各个区域的高度，
你可以选择从任意一个区域出发，并滑向任意一个周边的高度严格更低的区域（周边的定义是上下左右相邻的区域）。
请问整个滑雪场中最长的滑道有多长？(滑道的定义是从一个点出发的一条高度递减的路线）。
(本题和矩阵最长递增路径类似，该题是当年NOIP的一道经典题)

数据范围： 1≤n,m≤100 ，矩阵中的数字满足 1≤val≤1000

输入描述：

第一行输入两个正整数 n 和 m 表示矩阵的长宽。
后续 n 行输入中每行有 m 个正整数，表示矩阵的各个元素大小。

输出描述：

输出最长递减路线。

思路与矩阵中的最长递增路径一样

#include <functional>
#include <iostream>
#include <vector>
using namespace std;
int memo[101][101];
int n,m;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int main() {
    cin>>n>>m;
    vector<vector<int>> map(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>map[i][j];
        }
    }
    function<int(int,int)> dfs=[&](int i,int j)->int{
        if(memo[i][j]!=0) return memo[i][j];
        int ret=1;
        for(int k=0;k<4;k++){
            int x=i+dx[k];
            int y=j+dy[k];
            if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]<map[i][j]){
                ret=max(ret,dfs(x,y)+1);
            }
        }
        memo[i][j]=ret;
        return ret;
    };

    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            ans=max(ans,dfs(i,j));
        }
    }
    cout<<ans<<endl;

    return 0;
}

7迷宫问题

描述

定义一个二维数组 N*M ，如 5 × 5 数组下所示：

int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，
要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

数据范围： 2≤n,m≤10 ，输入的内容只包含 0≤val≤1

输入描述：

输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，
0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述：

左上角到右下角的最短路径，格式如样例所示。

经典BFS 和上述迷宫类似这里需要输出最佳路径

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int ROW,COL;
vector<vector<int>> maze;
vector<vector<bool>> visited;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

struct Node{
    int x,y;
    vector<pair<int,int>> path;
};

bool isValid(int i,int j){
    return (i>=0&&i<ROW&&j>=0&&j<COL&&maze[i][j]==0&&!visited[i][j]);
}

vector<pair<int,int>>bfs(vector<vector<int>>& maze){
    queue<Node> q;
    q.push({0,0,{{0,0}}});
    visited[0][0]=true;
    while(!q.empty()){
        Node cur=q.front();
        q.pop();

        if(cur.x==ROW-1&&cur.y==COL-1){
            return cur.path;
        }

        for(int k=0;k<4;k++){
            int newX=cur.x+dx[k];
            int newY=cur.y+dy[k];
            if(isValid(newX, newY)){
                visited[newX][newY]=true;
                vector<pair<int,int>> newpath=cur.path;
                newpath.push_back({newX,newY});
                q.push({newX,newY,{newpath}});
            }
        }
    }
    return {};
}

int main() {
    cin>>ROW>>COL;
    maze=vector<vector<int>>(ROW,vector<int>(COL));
    visited=vector<vector<bool>>(ROW,vector<bool>(COL,false));
    for(int i=0;i<ROW;i++){
        for(int j=0;j<COL;j++){
            cin>>maze[i][j];
        }
    }
    vector<pair<int,int>> path=bfs(maze);
    for(int i=0;i<path.size();i++){
        cout<<"("<<path[i].first<<","<<path[i].second<<")"<<endl;
    }
    return 0;
}

8红与黑

描述

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，
只能向相邻的（上下左右四个方向）黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入描述：

输入包含多组数据。
每组数据第一行是两个整数 m 和 n（1≤m, n≤20）。紧接着 m 行，每行包括 n 个字符。每个字符表示一块瓷砖的颜色，规则如下：

“.”：黑色的瓷砖；
“#”：白色的瓷砖；
“@”：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

输出描述：

对应每组数据，输出总共能够到达多少块黑色的瓷砖。

DFS

解答

#include <iostream>
using namespace std;
#include <vector>
int m, n;
vector<vector<char>> grid;
vector<vector<bool>> visited;
int startX, startY;
int count;

// 定义方向数组，上下左右四个方向
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 检查是否在网格范围内
bool isValid(int x, int y) {
    return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '.' &&
           !visited[x][y];
}

// 深度优先搜索
void dfs(int x, int y) {
    visited[x][y]=true;
    count++;
    for(int i=0;i<4;i++){
        int newX=x+dx[i];
        int newY=y+dy[i];
        if(isValid(newX, newY)){
            dfs(newX,newY);
        }
    }
}

int main() {
    while (cin >> m >> n) {
        grid=vector<vector<char>>(m,vector<char>(n));
        visited=vector<vector<bool>>(m,vector<bool>(n));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin>>grid[i][j];
                if(grid[i][j]=='@'){
                    startX=i;
                    startY=j;
                    grid[i][j]='.';
                }
            }
        }
        count=0;
        dfs(startX,startY);
        cout<<count<<endl;
    }
    return 0;
}

9树根

数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数，那么这个数就是数根；
如果结果是两位数或者包括更多位的数字，那么再把这些数字加起来。如此进行下去，直到得到是一位数为止。
比如，对于24 来说，把2 和4 相加得到6，由于6 是一位数，因此6 是24 的数根。
再比如39，把3 和9 加起来得到12，由于12 不是一位数，因此还得把1 和2 加起来，最后得到3，这是一个一位数，因此3 是39 的数根。
现在给你一个正整数，输出它的数根。

输入描述:

1 2	输入包含多组数据。每组数据数据包含一个正整数n（1≤n≤10E1000）。

输出描述:

1	对应每一组数据，输出该正整数的数根。

解答

#include <iostream>
using namespace std;
int rootNum(int num){
    int rootnum=0;
    while(num>0){
        rootnum+=num%10;
        num/=10;
    }
    while(rootnum>=10){
        rootnum=rootNum(rootnum);
    }
    return rootnum;
}

int main() {
    string str;
    while(cin>>str){
        int sum=0;
        for(auto ch:str){
            sum+=ch-'0';
        }
        cout<<rootNum(sum)<<endl;
    }
    return 0;
}

10跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
数据范围： 1≤n≤40
要求：时间复杂度： O(n) ，空间复杂度： O(1)

经典斐波那契数列

解答

#include <iostream>
using namespace std;
int Fib(int n){
    if(n<3) return n;
    else return (Fib(n-1)+Fib(n-2));
}

int main() {
    int n;
    cin>>n;
    cout<<Fib(n)<<endl;
    return 0;
}

11跳台阶扩展问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围： 1≤n≤20
进阶：空间复杂度 O(1) ，时间复杂度 O(1)

数据归纳
假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1)；
假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)；
假定第一次跳的是3阶，那么剩下的是n-3个台阶，跳法是f(n-3)……
假定第一次跳的是n-1阶，那么剩下的是1个台阶，跳法是f(1)；
假定第一次跳的是n阶，那么剩下的是0个台阶，跳法是1种；

总结 f(n)=2^(n-1)

解答

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    cout << (1 << (n - 1)) << endl;
    return 0;
}

1五子棋

2kotori和迷宫

3走迷宫

4幸运的袋子

5矩阵中的最长递增路径

6滑雪

7迷宫问题

8红与黑

9树根

10跳台阶

11跳台阶扩展问题