@Yezi.press
方向数组/偏移数组技巧
二维数组枚举、BFS/DFS 常用的方向数组技巧
Markdown发布于 2026/08/20编辑于 2026/10/29#方向数组
经常遇到一些题目,需要在二维数组中枚举某个点 a[i][j] 的周围四个方向的值,正常实现的话:
C++if (a[x-1][y] == 1) {...}; if (a[x+1][y] == 1) {...}; if (a[x][y-1] == 1) {...}; if (a[x][y+1] == 1) {...};
但一般还需要加入越界检测,所以...
C++if (x-1 >= 1 && a[x-1][y] == 1) {...}; if (x+1 <= n && a[x+1][y] == 1) {...}; if (y-1 >= 1 && a[x][y-1] == 1) {...}; if (y+1 <= m && a[x][y+1] == 1) {...};
俗话说得好,同样的代码片段不要出现超过两次,这里出现了四次,如果是周围八个方向或是更多的话,出现的次数只会更多,所以我们得考虑使用循环来解决问题了;
简单分析我们会发现,四个方向实际上都有个共同点,就是行下标 x 和列下标 y 都需要加一个数字:
C++a[x + (-1)][y + 0 ] // 上 a[x + 1 ][y + 0 ] // 下 a[x + 0 ][y + (-1)] // 左 a[x + 0 ][y + 1 ] // 右
我们将 x 和 y 增加的数字提取到 dx 和 dy 数组中,就可以得到:
C++int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 1 || nx > n || ny < 1 || ny > m) continue; if (a[nx][ny] == 1) ...... }
这就是 方向数组 或叫做 偏移数组。
那如果是八个方向的话:
C++int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1}; int dy[] = {0, 0, -1, 1, -1, 1, -1, 1}; for (int i = 0; i < 8; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 1 || nx > n || ny < 1 || ny > m) continue; if (a[nx][ny] == 1) ...... }
马走日:
C++int dx[8] = {-1, -1, 1, 1, -2, -2, 2, 2}; int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1}; for (int i = 0; i < 8; i++) { ...... }
搞定!😄