## 最後一個了 二維陣列走訪
二維陣列一般使用巢狀for迴圈走訪每個元素。
### 輸入
假設要讀入 m 列 n 行的矩陣：
```cpp=
int m, n;
cin >> m >> n;
int a[m][n];
for(int i=0; i<m; i++)
for (int j=0; j<n; j++)
cin >> a[i][j];
```
注意外圈的註標放在一維，內圈的註標放二維。
### 輸出
如果要求每列元素列印時間隔一個空白字元，且最後一個元素後面沒有空白字元，作法如下：
```cpp=
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (j==0) cout << a[i][j];
else cout << " " << a[i][j];
}
cout << "\n";
}
```
注意外圈要負責列印每列的換行符號。
### 鄰居走訪
假設陣列元素座標為 (x,y)，它的鄰居如下圖所示：
由圖可知，上下左右4個鄰居(底色為淡橘色)的座標：
- 上 (x-1, y)
- 下 (x+1, y)
- 左 (x, y-1)
- 右 (x, y+1)
假設目前位置是 (x, y)，各鄰居的位移量為 (a, b)，各鄰居的位置即為 (x+a, y+b)。鄰居位移量：
- 上鄰居的位移量是(-1,0)
- 下鄰居的位移量是(1, 0)
- 左鄰居的位移量是(0,-1)
- 右鄰居的位移量是(0, 1)
可以用一個二維陣列(方法一)或兩個一維陣列(方法二)來枚舉鄰居。
方法1：
```cpp=
const int mov[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
int x, y, nx, ny;
for (x=0; x<m; x++) {
for (y=0; y<n; y++) {
for (int i=0; i<4; i++) {
int nx = x+mov[i][0];
int ny = y+mov[i][1];
// 位置不合法跳過
if (nx<0 || nx>=m || ny<0 || ny>=n) continue;
// 處理 a[nx][ny]
// ...
// ...
}
}
}
```
上面的const是把變數值鎖住，讓它不能變更或修改
第9行是座標不合法就跳過不處理。
下面的程式是不給第一個陣列大小的寫法，真的可以這樣寫，但第二個陣列一定要有值：
```cpp=
const int mov[][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
```
枚舉上、下、左、右、左上、右上、左下、右下 觀察到對角線鄰居(上圖底色為淺綠)的位移量規則為$(\pm1, \pm1)$，可知8鄰居位移量的二維陣列寫法：
```cpp=
const int mov[][2]={{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}};
```
:::success
走訪位移量的可能(我掰的)
$(0,\pm1), (\pm1,0), (\pm1,\pm1)$
:::
## 炸彈偵測器
題目：[f149. 炸彈偵測器](https://zerojudge.tw/ShowProblem?problemid=f149)
:::spoiler 參考程式
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int R,C;
cin >> R >> C;
int a[R][C];
int all_bomb=0, remove_bomb=0;
for (int i=0; i<R; i++) {
for (int j=0; j<C; j++) {
cin >> a[i][j];
if (a[i][j]==1) all_bomb++;
}
}
const int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{1,1},{1,-1},{-1,1}};
int x,y,nx,ny;
for (x=0; x<R; x++) {
for (y=0; y<C; y++) {
// 如果a[x][y]不是5就跳過
if (a[x][y]!=5) continue;
// a[x][y]為偵測器
bool again=false; // 8個鄰居有偵測器，要設為true
// 檢查8個鄰居是否有5(偵測器)
for (int i=0; i<8; i++) {
nx = x+mov[i][0];
ny = y+mov[i][1];
if (nx>=0 && nx<R && ny>=0 && ny<C) {
if (a[nx][ny]==5) {
again=true;
break;
}
}
}
if (again) continue;
// 搜尋可移除的炸彈
// 再次搜尋8個鄰居是否有1
for (int i=0; i<8; i++) {
nx = x+mov[i][0];
ny = y+mov[i][1];
if (nx>=0 && nx<R && ny>=0 && ny<C) {
if (a[nx][ny]==1) {
a[nx][ny]=0;
remove_bomb++;
}
}
}
}
}
cout << remove_bomb << " " << all_bomb-remove_bomb;
}
```
:::
## Box of Bricks
題目：[c067. Box of Bricks](https://zerojudge.tw/ShowProblem?problemid=c067)
想法：最小搬動數等於每堆積木數與平均積木數的差值絕對值總和的一半。
:::spoiler 參考程式
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
int cases=1;
while(cin>>n) {
if (n==0) break;
int a[n];
int total=0; // 積木總數
for(int i=0; i<n; i++) {
cin>>a[i];
total+=a[i];
}
// 計算高度
int h = total/n;
// 計算積木搬動個數
int mov=0;
for (int i=0; i<n; i++) {
mov+=abs(a[i]-h);
}
mov/=2;
cout << "Set #" << cases << "\n";
cout << "The minimum number of moves is " << mov << ".\n\n";
cases++;
}
return 0;
}
```
:::
## 特殊位置
題目：[k732. 特殊位置](https://zerojudge.tw/ShowProblem?problemid=k732)
:::spoiler 參考程式
```cpp=
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int n,m;
cin>>n>>m;
int a[n][m];
vector<pair<int,int>> v; // 儲存特殊位置
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
cin>>a[i][j];
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
int x=a[i][j];
// 找到曼哈頓距離小於等於x座標，計算點數和
int sum=0;
for (int ii=0; ii<n; ii++) {
for (int jj=0; jj<m; jj++) {
if (abs(ii-i)+abs(jj-j)<=x)
sum+=a[ii][jj];
}
}
if (sum%10==x) v.push_back({i,j});
}
}
cout << v.size() << endl;
for(auto& x:v) cout << x.first << " " << x.second << endl;
return 0;
}
```
:::
## 賓果遊戲
題目：[b548. 賓果遊戲](https://zerojudge.tw/ShowProblem?problemid=b548)
:::spoiler sol
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a[5][5];
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
cin >> a[i][j];
int num;
while (cin >> num && num!=-1)
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
if (num == a[i][j]) a[i][j] = 0;
vector<int> b(26); // index i 的陣列值表示賓果數字 i 的得分
// 檢查每列會得分的數字
int cnt; // 記錄已經消除數字的數量
for (int i = 0; i < 5; i++) {
cnt = 0;
for (int j = 0; j < 5; j++) {
if (a[i][j] == 0)
cnt++;
}
if (cnt == 4) {
for (int k = 0; k < 5; k++) {
num=a[i][k];
if (num != 0) {
b[num]++;
}
}
}
}
// 檢查每行會得分的數字
for (int j = 0; j < 5; j++) {
cnt = 0;
for (int i = 0; i < 5; i++) {
if (a[i][j] == 0)
cnt++;
}
if (cnt == 4) {
for (int k = 0; k < 5; k++) {
num = a[k][j];
if (num != 0) {
b[num]++;
}
}
}
}
// 右下左上對角線檢查
cnt = 0;
for(int i = 0; i < 5; i++) {
if (a[i][i]==0) cnt++;
}
if(cnt == 4) {
for(int i = 0; i < 5; i++) {
num = a[i][i];
if(num != 0) {
b[num]++;
}
}
}
// 右上左下對角線檢查
cnt = 0;
for (int i = 0, j = 4; i < 5; i++,j--) {
if(a[i][j]==0) cnt++;
}
if (cnt == 4) {
for(int i = 0, j = 4; i < 5; i++, j--) {
num = a[i][j];
if(num != 0) {
b[num]++;
}
}
}
int mx = -1;
for(int i = 1; i<=25; i++)
mx = max(mx, b[i]);
for(int i = 1; i<=25; i++) {
if(b[i]==mx) {
cout << i;
break;
}
}
return 0;
}
Sign in with Wallet
Connect another wallet