T1[斐波拉契蛇形矩阵]

题意

看样例应该能看懂

示例1

样例输入

3

样例输出

34 21 13
1 1 8
2 3 5

限制

$n < 10$

C++ 代码

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

typedef long long LL;

int n;
vector<LL> A = {1, 1};
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
vector<vector<LL>> ret;

int main() {
    cin >> n;
    if (n == 1) cout << 1;
    else {
        for (int i = 2; i <= n * n - 1; i ++ ) A.push_back(A[i - 1] + A[i - 2]);
        ret = vector<vector<LL>>(n, vector<LL>(n, 0));

        for (int i = 0, j = 0, k = A.size() - 1, d = 0; k >= 0; k -- ) {
            ret[i][j] = A[k];
            int a = i + dx[d], b = j + dy[d];
            if (a < 0 || b < 0 || a >= n || b >= n || ret[a][b]) {
                d = (d + 1) % 4;
                a = i + dx[d], b = j + dy[d];
            }
            i = a, j = b;
        }

        for (int i = 0; i < n; i ++ ) {
            for (int j = 0; j < n; j ++ )
                cout << ret[i][j] << ' ';
            cout << endl;
        }
    }

    return 0;
}

T2[矩阵中的单词查找]

题意

找CHINA

示例1

样例输入

4
CHIA
CANT
GRAC
BBDE

样例输出

2

限制

$n <= 30$

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 35;

int n, ret;
string c = "CHINA";
char g[N][N];

void dfs(int x, int y, int s) {
    if (g[x][y] != c[s]) return;
    if (s == c.size() - 1) {
        ret ++ ;
        return;
    }

    char t = g[x][y];
    g[x][y] = '#';

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

    g[x][y] = t;
}

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

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            dfs(i, j, 0);

    cout << ret;

    return 0;
}

题目描述懒得写了，应该多花点时间在选择题上的