#include <iostream>
#include <cstring>

using namespace std;

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

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 (0 <= a && a < n && 0 <= b && b < n && st[a][b] == false) {
            if (dfs(a, b) == true) return true; // 只要有一个分支是可达的那就返回true
        }
    }
    return false;
}

int main() {
    cin >> k;
    while (k --) {
        cin >> n;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                cin >> g[i][j];
            }
        }
        cin >> xa >> ya >> xb >> yb;
        memset(st, false, sizeof st);

        if (dfs(xa, ya) == true) puts("YES");
        else puts("NO");

    }

    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 22;
int n, m, x, y;
char g[N][N];
bool st[N][N];
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

// dfs：每个格子是一个状态，所以不需要恢复现场
int dfs(int x, int y) {
    int cnt = 0;
    st[x][y] = true;
    cnt ++;

    for (int i = 0; i < 4; i ++) {
        int a = x + dx[i], b = y + dy[i];
        if (0 <= a && a < n && 0 <= b && b < m) {
            if (g[a][b] == '#') continue;
            if (st[a][b] == true) continue;
            cnt += dfs(a, b);

        }
    }

    return cnt;
}

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

    return 0;
}

class Solution {
public:
    // 这里的s[j]一定是正整数
    // 如何枚举所有的区间[j + 1, i]的和
    // 固定i, (s[i] - s[j]) % k == 0
    // s[i] % k - s[j] % k = 0
    // 固定i：s[j] % k == s[i] % k - 0（看一下是否存在）
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> s(n + 1, 0);
        for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + nums[i - 1];

        unordered_map <int, int> hash;
        // 长度要大于等于2，所以j <= i - 2的 s[j] % k都放到哈希表里面
        for (int i = 2; i <= n; i ++) {
            hash[k == 0 ? s[i - 2] : s[i - 2] % k] = 1;
            int t = k == 0 ? s[i] : s[i] % k;
            if (hash.count(t - 0) != 0) return true;
        }

        return false;
    }
};

class Solution {
public:
    // 类似第一题
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> s(n + 1, 0);
        for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + nums[i - 1];

        unordered_map <int, int> hash; // 存每个前缀和出现的次数
        int res = 0;
        hash[s[0]] ++;
        // 枚举每个i，看现有hash表中有多少个前缀和等于s[i] - k
        for (int i = 1; i <= n; i ++) {
            res += hash[s[i] - k];
            hash[s[i]] ++; // 把当前的前缀和s[i]加入哈希表，进入下一轮
        }
        return res;
    }
};

#include <iostream>
#include <cmath>

using namespace std;

const int N = 200, INF = 0x3f3f3f3f;
int n, x, y;
char g[N][N]; // 领接矩阵 
double maxd[N];
double d[N][N];

struct Pos{
    int x, y;
}pos[N];

double getEdge(int i, int j) {
    int x1 = pos[i].x, x2 = pos[j].x, y1 = pos[i].y, y2 = pos[j].y;
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main() {
    cin >> n;
    // 每个点用1,2,...n表示
    for (int i = 1; i <= n; i ++) {
        cin >> pos[i].x >> pos[i].y; // 读入每个点的坐标
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            cin >> g[i][j]; 
            if (g[i][j] == '1') {
                d[i][j] = getEdge(i, j);
            } else d[i][j] = INF;
        }
    }

    // 用floyd算出每两个点之间的最短距离
    for (int i = 1; i <= n; i ++) d[i][i] = 0;
    for (int k = 1; k <= n; k ++) {
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= n; j ++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }

    }

    // 计算每个点的最短距离中最远的点的距离maxd[i];
    double r = 0;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            if (i != j && d[i][j] < INF / 2) {
                maxd[i] = max(maxd[i], d[i][j]);
            }
        }
        r = max(r, maxd[i]); // 原来牧场1,2,..的直径的最大值（可能有多个不连通的牧场）
    }

    // 遍历所有dist[i, j] = 无穷
    double res = INF; // 维护最小的直径
    for (int i = 1; i <= n; i ++) {
        for (int j = i; j <= n; j ++) {
            if (d[i][j] > INF / 2) { // 不连通的两个点
                double ds = maxd[i] + maxd[j] + getEdge(i, j);
                res = min(res, max(r, ds));               
            }
        }
    }

    printf("%.6f", res);

    return 0;
}

如果读数据要读$10^5$以上的次数，那建议用scanf或者优化cin

这个题m,k,d最大可以是1e6

优化cin

// 多源bfs模板题
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N =  1e3 + 7;
typedef pair<int, int> PII;
typedef long long LL;
int n, m, k, d;
int x, y, c;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
LL numbers[N][N];
int dist[N][N];
char g[N][N];


int main() {
    std::ios::sync_with_stdio(false); // 必须关闭stdin同步，不然cin会超时

    // 方格图的大小、栋栋的分店数量、客户的数量，以及不能经过的点的数量
    cin >> n >> m >> k >> d;

    queue<PII> q;
    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= n; j ++) g[i][j] = 'o';
    for (int i = 1; i <= m; i ++) {
        cin >> x >> y;
        g[x][y] = '*'; // 分店
        dist[x][y] = 0;
        q.push({x, y}); // 多源bfs 起点
    }

    for (int i = 1; i <= k; i ++) {
        cin >> x >> y >> c;
        g[x][y] = '.'; // 客户
        numbers[x][y] += c;

    }

    for (int i = 1; i <= d; i ++) {
        cin >> x >> y;
        g[x][y] = '#'; // 障碍物
    }

    // 计算dist距离
    while (q.size()) {
        auto t = q.front();
        q.pop();
        int x = t.first, y = t.second;
        for (int d = 0; d < 4; d ++) {
            int a = x + dx[d], b = y + dy[d];
            if (1 <= a && a <= n && 1 <= b && b <= n && g[a][b] != '#') {
                if (dist[a][b] == 0x3f3f3f3f) {
                    dist[a][b] = dist[x][y] + 1;
                    q.push({a, b});
                }
            }
        }
    }

    LL res = 0;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            if (g[i][j] == '.') {
                res += (numbers[i][j] * 1ll * dist[i][j]);
            }
        }
    }

    cout << res << endl;

    return 0;
}

scanf

// 多源bfs模板题
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N =  1e3 + 7;
typedef pair<int, int> PII;
typedef long long LL;
int n, m, k, d;
int x, y, c;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
LL numbers[N][N];
int dist[N][N];
char g[N][N];

struct Target
{
    int x, y, c;
}tg[N * N];


int main() {
    // 方格图的大小、栋栋的分店数量、客户的数量，以及不能经过的点的数量
    scanf("%d%d%d%d", &n, &m, &k, &d);
    // cin >> n >> m >> k >> d;

    queue<PII> q;
    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= n; j ++) g[i][j] = 'o';
    for (int i = 1; i <= m; i ++) {
        // scanf("%d%d", &x, &y);
        cin >> x >> y;
        g[x][y] = '*'; // 分店
        dist[x][y] = 0;
        q.push({x, y}); // 多源bfs 起点
    }

    for (int i = 1; i <= k; i ++) {
         scanf("%d%d%d", &tg[i].x, &tg[i].y, &tg[i].c);
        // cin >> x >> y >> c;
        // tg[i] = {x, y, c};

    }

    for (int i = 1; i <= d; i ++) {
          scanf("%d%d", &x, &y);
        // cin >> x >> y;
        g[x][y] = '#'; // 障碍物
    }

    // 计算dist距离
    while (q.size()) {
        auto t = q.front();
        q.pop();
        int x = t.first, y = t.second;
        for (int d = 0; d < 4; d ++) {
            int a = x + dx[d], b = y + dy[d];
            if (1 <= a && a <= n && 1 <= b && b <= n && g[a][b] != '#') {
                if (dist[a][b] == 0x3f3f3f3f) {
                    dist[a][b] = dist[x][y] + 1;
                    q.push({a, b});
                }
            }
        }
    }

    LL res = 0;
    for (int i = 1; i <= k; i ++) {
         res += dist[tg[i].x][tg[i].y] * tg[i].c;
    }

    cout << res << endl;

    return 0;
}

#include <iostream>

using namespace std;

const int N = 1e3 + 10;
int f[N];
int n, m;

int main() {
    cin >> m >> n;

    for (int i = 1; i <= n; i ++) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j --) {
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    cout << f[m] << endl;

    return 0;
}

class Solution {
public:
    // 在归并排序求逆序对的基础上额外去求下a[i] > 2 * a[j]（因为我只要用有序这个条件即可）
    typedef long long LL; // 数据量较大要用long long
    static const int N = 50010;
    LL res = 0; // 统计翻转对数
    LL q[N], tmp[N];

    void solve(LL q[], int l, int r) {
        if (l >= r) return;
        int mid = l + r >> 1;
        // 递归：相信他能完成任务（计算他那部分翻转对）
        solve(q, l, mid), solve(q, mid + 1, r); 

        // 双指针的思想去求两个子问题之间的翻转对
        int i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (q[i] > 2 * q[j]) {
                res += mid - i + 1;
                j ++;
            } else i ++;
        }

        // 归并：合二为一
        i = l, j = mid + 1;
        int k = l;
        while (i <= mid && j <= r) {
            if (q[i] <= q[j]) tmp[k ++] = q[i ++];
            else tmp[k ++] = q[j ++];
        }
        while (i <= mid) tmp[k ++] = q[i ++];
        while (j <= r) tmp[k ++] = q[j ++];

        for (int i = l; i <= r; i ++) q[i] = tmp[i];

    }

    int reversePairs(vector<int>& a) {
        int n = a.size();
        for (int i = 0; i < n; i ++) q[i] = a[i];

        solve(q, 0, n - 1);
        return res;
    }
};

这个题我们发现手中有货和手中无货这两个状态已经不够用了。因为我们还需要去表示冷冻期这个概念。即我们还要把手中无货这个状态再细分成两个不同的状态。

这个题没有设置交易次数，所以我们不需要用到 $j$

状态机

状态表示：
- $f[i][0]$表示只考虑前 $i$ 天且手中有货的最大收益
- $f[i][1]$表示只考虑前 $i$ 天且目前处于手中无货的第 1 天的最大收益
- $f[i][2]$表示只考虑前 $i$ 天且目前处于手中无货的第 $\geqslant 2$天的最大收益

推荐题解：用状态机分析法

#include <iostream>

using namespace std;

const int N = 1e5 + 7;
int w[N], f[N][3];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++) cin >> w[i];

    // 初始化 出现 i - 1
    // 入口设为0，其余边界设为-INF
    f[0][2] = 0, f[0][0] = f[0][1] = -0x3f3f3f3f; // 不合法的状态设为-INF，这样一定不会用来更新后面的状态。


    // 状态计算
    for (int i = 1; i <= n; i ++) {
        f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
        f[i][1] = f[i - 1][0] + w[i];
        f[i][2] = max(f[i - 1][2], f[i - 1][1]); // 这里没有了交易次数的限制
    }

    // 问题答案
    cout << max(f[n][1], f[n][2]) << endl; // 所有可能的出口取max

    return 0;
}

状态表示：

$f[i][j][0]$表示所有只考虑前 $i$ 天且已经进行完 $j$ 次交易，且手中无货的所有的购买方式的集合

$f[i][j][1]$表示所有只考虑前 $i$ 天且已经进行完 $j - 1$ 次交易，并且正在进行第 $j$ 次交易，并且手中有货的所有的购买方式的集合

初始化：

[1] 如果一种状态不合法，或者不希望从这个状态转移过来 ，那么就把它设成正无穷或负无穷
因为这个题要求最大值，所以把不合法的设成负无穷，也这样这个状态不可能用来更新后来的状态

核心：如何把一次交易描述清楚

注意：是看当天结束时处于什么状态

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 7;

int w[N];
int f[N][110][2];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) cin >> w[i];

    // 初始化
    memset(f, -0x3f, sizeof f);
    for (int i = 0; i <= n; i ++) f[i][0][0] = 0; // 入口设为0，其余设为-INF，表示不合法

    // 状态机状态表示 + 状态计算
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= k; j ++) {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
        }
    }

    // 问题答案
    int res = 0;
    for (int j = 0; j <= k; j ++) { // 0次交易也算在内的
        res = max(res, f[n][j][0]); // 所有可能的出口
    }

    cout << res << endl;

    return 0;
}