seansie's blog

zerojudge f149 3. 炸彈偵測器 (Detector) C++詳解 | seansie blog

題目

https://zerojudge.tw/ShowProblem?problemid=f149

總之，題目會先給定兩個數字 R 跟C 分別代表 row 跟 column 的數目，然後會輸入地圖，如以下格式。

  • 5 代表偵測器
  • 0 代表空地
  • 1 代表炸彈

偵測器的感測範圍是在他所在的座標，往外8方向延伸的8個格子(上下左右 左上 左下 右上 右下 )

但不幸的是，如果在感測範圍有其他偵測器的話，感測器會一起失靈

請輸出能被偵測到的炸彈根部能偵測到的。

破題

這個題目看似簡單，裡面陷阱不少。

首先先把地圖讀進去吧

	scanf("%d %d", &r, &c);
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			scanf("%d", &g[i][j]);
		}
	}

然後有個關鍵就是要處理互相干擾的問題，我的處理方法是再建立一個 bfield 二維矩陣，用來記錄有互相干擾的偵測器

int bfield[r][c];
memset(bfield, 0, sizeof(bfield)); // 記得初始化 這個意思是把 bfiled 變數全部設定成 0

接著對於外面的八個方向，建議儲存成陣列，然後用迴圈的方式一一處理

int dir[8][2] = {
		{0, -1},
		{0, 1},
		{-1, 0},
		{1, 0},
		{-1, -1},
		{1, -1},
		{-1, 1},
		{1, 1}
		};

很明顯在邊界的偵測器，會出現越界問題，因此還需要加上越界檢查，建議使用一個函數來處理

bool isValid(int x, int y, int r, int c)
{
	return (x >= 0 && x < r && y >= 0 && y < c); //檢查上下左右界使否越界
}

然後開始逐偵測器掃描旁邊是否有偵測器(即地圖上的元素=5的情況)，若有，在 bfield 矩陣上標記 -1

for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			if (g[i][j] == 5)
				for (int k = 0; k < 8; k++)
					if (isValid(i + dir[k][0], j + dir[k][1], r, c))
					{
						if (g[i + dir[k][0]][j + dir[k][1]] == 5)
						{
							bfield[i + dir[k][0]][j + dir[k][1]] = -1, g[i][j] = -1;
						}
					}

為甚麼不直接修改 g[i][j] 呢，因為偵測器會互相影響，如果移除了其中一個，會漏移除剩下的互相干擾的偵測器。

而裡面的8方位是透過以下的方式來處理的

for (int k = 0; k < 8; k++)
					if (isValid(i + dir[k][0], j + dir[k][1], r, c))
					{
						if (g[i + dir[k][0]][j + dir[k][1]] == 5)
						{
							bfield[i + dir[k][0]][j + dir[k][1]] = -1, g[i][j] = -1;
						}
					}

用迴圈來遍歷所有儲存在 dir 的方向，然後新方向用 x+dir[k][0] y+dir[k][1] 表示

x,y是目前座標

接著基於 bfiled 的資訊來修改 g[i]j[j]，具體來說是把被干擾的偵測器，在地圖上從5改成0

for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			if(bfield[i][j]==-1){
				g[i][j]=0;
			}
		}
	}

然後還要建立 bomb 二維矩陣，用來記錄炸彈被偵測的資訊，特別建立這個矩陣的原因是因為可能同一個炸彈會被不同偵測器偵測數次，如果只是單純計數的話，會多算不少炸彈。

int bomb[r][c]
memset(bomb, 0, sizeof(bomb)); // 記得初始化 這個意思是把 bomb 變數全部設定成 0

移除完受干擾的偵測器後，現在可以開始對元素一一處理了，現在有兩個東西要處理

  • 偵測器，掃描周圍至多8個方格，如果有炸彈，在 bomb 上標記 1
  • 炸彈: 這個也要記錄，因為我們要輸出未偵測的炸彈數量，而這個數量可以透過全部減去偵測出來的炸彈計算出來。 計算方法就遇到 g[i][j]==1 的時候加1就好。
for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (g[i][j] == 5)
			{
				for (int k = 0; k < 8; k++)
				{
					if (isValid(i + dir[k][0], j + dir[k][1], r, c))
					{
						if (g[i + dir[k][0]][j + dir[k][1]] == 1)
						{
							bomb[i + dir[k][0]][j + dir[k][1]] = 1;
						}
					}
				}
			}
			else if (g[i][j] == 1)
			{
				all++;
			}
		}
	}

最後基於剛剛計算出來的 bomb 來推測有幾顆炸彈被偵測出來。

for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			if (bomb[i][j] == 1)
				detected++;

最後印出來

printf("%d %d", detected, all - detected);

完整程式碼

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

bool isValid(int x, int y, int r, int c)
{
	return (x >= 0 && x < r && y >= 0 && y < c);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int r, c, detected = 0, all = 0;
	scanf("%d %d", &r, &c);
	int dir[8][2] = {
		{0, -1},
		{0, 1},
		{-1, 0},
		{1, 0},
		{-1, -1},
		{1, -1},
		{-1, 1},
		{1, 1}};
	int g[r][c], bomb[r][c], bfield[r][c];
	memset(bomb, 0, sizeof(bomb));
	memset(bfield, 0, sizeof(bfield));
	// bad -1
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			scanf("%d", &g[i][j]);
		}
	}

	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			if (g[i][j] == 5)
				for (int k = 0; k < 8; k++)
					if (isValid(i + dir[k][0], j + dir[k][1], r, c))
					{
						if (g[i + dir[k][0]][j + dir[k][1]] == 5)
						{
							bfield[i + dir[k][0]][j + dir[k][1]] = -1, g[i][j] = -1;
						}
					}
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			if(bfield[i][j]==-1){
				g[i][j]=0;
			}
		}
	}

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (g[i][j] == 5)
			{
				for (int k = 0; k < 8; k++)
				{
					if (isValid(i + dir[k][0], j + dir[k][1], r, c))
					{
						if (g[i + dir[k][0]][j + dir[k][1]] == 1)
						{
							bomb[i + dir[k][0]][j + dir[k][1]] = 1;
						}
					}
				}
			}
			else if (g[i][j] == 1)
			{
				all++;
			}
		}
	}
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			if (bomb[i][j] == 1)
				detected++;
	printf("%d %d", detected, all - detected);
	return 0;
}

AC (3ms, 372KB)