二维坐标映射一维数字

目录

最常用：行优先映射（Row-major Order）

核心公式（默认 x 是行号，y 是列号）

示例（好记）

关键前提

题目应用

最常用：行优先映射（Row-major Order）

这是最直观、工程中最常用的方式，本质是 “按行遍历，依次编号”，适用于x、y 有明确范围（如矩阵、网格）的场景（比如题目中 x∈[0, n-1]，y∈[0, m-1]）。

核心公式（默认 x 是行号，y 是列号）

• 一维索引 idx = x * m + y（m 是每一行的列数，即 y 的最大取值 + 1；若 x、y 从 1 开始，调整为 idx = (x-1)*m + (y-1)）
• 反向映射（从 idx 找回 (x, y)）：x = idx //m （整数除法，向下取整）y = idx % m （取余）

示例（好记）

假设网格是 3 行（x=0,1,2）、4 列（y=0,1,2,3），m=4：

• (0,0) → 04+0=0；(0,3)→04+3=3
• (1,0) →14+0=4；(2,3)→24+3=11
• 反向：idx=7 → x=7//4=1，y=7%4=3 → (1,3)，完全唯一

关键前提

x 和 y 的范围固定（已知行数 n、列数 m），且 x、y 均在 [0, n-1]、[0, m-1] 内（无越界）。

题目应用

AtCoder C - 2x2 Placinghttps://atcoder.jp/contests/abc436/tasks/abc436_c使用map存每一个坐标的映射，然后直接判断即可

#include <bits/stdc++.h> using namespace std; #define int long long // priority_queue<int, vector<int>, greater<int> > q; const int N = 4e5+10; const int inf=1e18; void solve() { int n, m; cin >> n >> m; map<int,int>p; int ans=0; while (m--) { int r,c; cin >> r >> c; if (!p[r*n+c]&&!p[(r+1)*n+c]&&!p[r*n+(c+1)]&&!p[(r+1)*n+(c+1)]) { ans++; p[r*n+c]++; p[(r+1)*n+c]++; p[r*n+(c+1)]++; p[(r+1)*n+(c+1)]++; } } cout << ans << endl; } signed main() { int q=1; // cin >> q; while (q--) { solve(); } return 0; }