---
# System prepended metadata

title: APCS電子畫布
tags: [APCS, 解析]

---

# **APCS電子畫布**
:::    warning
題目:
https://zerojudge.tw/ShowProblem?problemid=o077
:::
***
這題我是用bfs做，但後來做完才發現測資很小，直接遍歷也不會超時
***
:::success
完整程式碼
:::
```cpp=
#include<iostream>
#include<queue>
#include<utility>
#include<cmath>
using namespace std;
int map[1000][1000];
void bfs(int r, int c, int t, int x)
{
	map[r][c] += x;
	bool visited[1000][1000] = { 0 };
	visited[r][c] = 1;
	queue<pair<int, int>> q;
	q.push(make_pair(r, c));
	int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
	while (q.size())
	{
		pair<int, int> p = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int newx = p.first + dx[i], newy = p.second + dy[i];
			if (newx < 0 || newy < 0 || newx >= 1000 || newy >= 1000) continue;
			if (abs(r - newx) + abs(c - newy) <= t && visited[newx][newy] == 0) 
                       //曼哈頓距離小於t且還沒走過
			{
				map[newx][newy] += x;
				visited[newx][newy] = 1;
				q.push(make_pair(newx, newy));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int h = 0, w = 0, n = 0;
	cin >> h >> w >> n;

	for (int i = 0; i < n; i++)
	{
		int r, c, t, x;
		cin >> r >> c >> t >> x;
		bfs(r, c, t, x);
	}

	
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
			cout << map[i][j] << " ";

		cout << "\n";
	}
	return 0;
}

```
:::success
掰掰:D
:::