07 · 二维数组与网格坐标

前面几节的数组只有一个下标，是一条“线”。网格题的数组有两个下标：a[i][j]。下标从 1 个变 2 个，错的种类也翻倍：行列写反、越界没判、方向数组配错，这三类占了入门阶段网格题 WA 的绝大多数。这一节把这三件事逐个钉死。

第一个下标 i 是行，从上往下增大；第二个下标 j 是列，从左往右增大。数学课上的点 (x, y) 是 x 向右、y 向上，和这里正好差一次转置——题目给你 (x, y) 时，先在纸上改写成 (行, 列)，再动键盘。同一份代码里同时出现两种约定，是查三小时也查不出来的那种错。

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

const int N = 105;
int a[N][N];                  // 全局：自动全 0，也不占栈

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];   // 第 i 行第 j 列

    a[1][2] = 7;              // 第 1 行第 2 列，不是第 2 行第 1 列
    cout << a[1][2] << "\n";  // 7
    cout << a[2][1] << "\n";  // 这是输入读进来的第 2 行第 1 列，和上面的 7 毫无关系
    return 0;
}

const int dx[4] = {0, 1, 0, -1};   // 右 下 左 上
const int dy[4] = {1, 0, -1, 0};

// 站在 (r,c)，看四个邻居分别是哪一格
for (int d = 0; d < 4; ++d) {
    int nr = r + dx[d];
    int nc = c + dy[d];
    if (nr < 1 || nr > n || nc < 1 || nc > m) continue;  // 先判边界
    // 到这里 (nr,nc) 一定在棋盘内，可以放心访问
}

第一个例子选扫雷：它把“访问邻居”和“判边界”这两件事同时用上，而且不用任何别的算法。

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

char g[105][105];                       // 全局：自动清零，也不吃函数栈

// 8 个方向：上、右上、右、右下、下、左下、左、左上（顺时针一圈）
const int dx[8] = {-1, -1,  0,  1, 1, 1, 0, -1};
const int dy[8] = { 0,  1,  1,  1, 0, -1, -1, -1};

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> g[i][j];             // char 版 cin 只取一个非空白字符，换行被自动跳过

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (g[i][j] == '*') {       // 雷格原样输出，不用数
                cout << '*';
                continue;
            }
            int cnt = 0;
            for (int d = 0; d < 8; ++d) {
                int ni = i + dx[d], nj = j + dy[d];
                // 顺序不能反：边界不合法时，g[ni][nj] 已经是数组外的内存
                if (ni < 1 || ni > n || nj < 1 || nj > m) continue;
                if (g[ni][nj] == '*') ++cnt;
            }
            cout << cnt;                // 输出 0~8，不加空格、不加分隔符
        }
        cout << '\n';                   // 一整行输出完才换行
    }
    return 0;
}

扫雷是“站在一格看周围”。第二类网格题是“沿着一条路一直走”：从某格出发，每步换个方向。典型代表就是蛇形方阵——它看起来是打印题，本质是状态机。

// 站在 (r,c)、朝向 dir，问下一步去哪
int nr = r + dx[dir], nc = c + dy[dir];
if (nr < 1 || nr > n || nc < 1 || nc > n || a[nr][nc] != 0) {
    dir = (dir + 1) % 4;                    // 撞墙或撞到旧数字：右转
    nr = r + dx[dir], nc = c + dy[dir];     // 转向后用新方向再算一次
}

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

int a[15][15];                          // 全局：全 0，用 0 表示“还没写过”

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

    const int dx[4] = {0, 1, 0, -1};     // 右 下 左 上
    const int dy[4] = {1, 0, -1, 0};
    int r = 1, c = 1, dir = 0;          // 从左上角出发，朝右

    for (int k = 1; k <= n * n; ++k) {
        a[r][c] = k;                    // 每走一步就写一个数
        if (k == n * n) break;          // 最后一格写完后不再预判，免得算出界外坐标

        int nr = r + dx[dir], nc = c + dy[dir];
        // 出界 or 撞到自己写过的数字，就顺时针转 90° 再试一次
        if (nr < 1 || nr > n || nc < 1 || nc > n || a[nr][nc] != 0) {
            dir = (dir + 1) % 4;
            nr = r + dx[dir], nc = c + dy[dir];
        }
        r = nr; c = nc;                 // 只有合法才真正前进
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) printf("%3d", a[i][j]);   // 题目要求 3 字符宽
        printf("\n");                   // 一行结束才换行
    }
    return 0;
}

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

bool lit[105][105];                 // lit[i][j] = 这一格有没有光；全局自动全 false

// 火把照亮的 13 个偏移：曼哈顿距离 <= 2，也就是 (0,0) + 4 个距离 1 + 8 个距离 2
const int tx[13] = { 0, -1, 1,  0, 0, -1, 1, -1, 1, -2, 2,  0, 0};
const int ty[13] = { 0,  0, 0, -1, 1, -1, -1, 1, 1,  0, 0, -2, 2};

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

    for (int t = 0; t < m; ++t) {
        int x, y;
        cin >> x >> y;
        for (int d = 0; d < 13; ++d) {
            int nx = x + tx[d], ny = y + ty[d];
            if (nx < 1 || nx > n || ny < 1 || ny > n) continue;  // 照到方阵外面的部分不算
            lit[nx][ny] = true;
        }
    }

    for (int t = 0; t < k; ++t) {
        int x, y;
        cin >> x >> y;
        // 萤石是完整的 5×5：两重循环直接生成 25 个偏移，不需要表
        for (int dx = -2; dx <= 2; ++dx)
            for (int dy = -2; dy <= 2; ++dy) {
                int nx = x + dx, ny = y + dy;
                if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
                lit[nx][ny] = true;
            }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (!lit[i][j]) ++ans;  // 一次都没被照到
    cout << ans << '\n';
    return 0;
}