模拟：[ABC182E] Akari 题解

洛谷题解，原链接：link。

思路简述

本题是一道比较基础的模拟题。

考虑到直接暴力枚举会超时，这里我们将暴力的代码优化一下。

建立一个地图二维数组 $a$ ，具体的值代表的意义详见代码注释。

我们可以用 $4$ 次双重循环，进行扫描，方向分别向上、下、左、右。

如果遇到障碍物，当前方向的灯光就会被阻止；

如果遇到灯光，当前方向的灯光就会发出（前提是之前没有灯光发向这边或被阻挡）；

否则遇到空地就可以将当前的灯的状态赋值给空地的状态了。

思路部分完结。

代码及注释

#include
using namespace std;int a[1505][1505];
/*a代表地图数组，0代表黑的空位，1代表灯泡，2代表障碍物,3代表亮的空位。*/
int n, m;
int q1, q2;int main() {int ans = 0;cin >> n >> m >> q1 >> q2;while (q1--) {int x, y;cin >> x >> y;a[x][y] = 1;ans++;}while (q2--) {//输入障碍物位置int x, y;cin >> x >> y;a[x][y] = 2;}bool haveLight = false;//使用haveLight变量记录是否有光for (int i = 1; i <= n; i++) {//向右扫haveLight = false;for (int j = 1; j <= m; j++) {if (a[i][j] == 2) {haveLight = false;continue;}if (a[i][j] == 1) {haveLight = true;continue;}if (a[i][j] == 3) continue;if (haveLight && a[i][j] == 0) a[i][j] = 3, ans++;}}for (int i = 1; i <= n; i++) {//向左扫haveLight = false;for (int j = m; j >= 1; j--) {if (a[i][j] == 2) {haveLight = false;continue;}if (a[i][j] == 1) {haveLight = true;continue;}if (a[i][j] == 3) continue;if (haveLight && a[i][j] == 0) a[i][j] = 3, ans++;}}for (int j = 1; j <= m; j++) {//向下扫haveLight = false;for (int i = 1; i <= n; i++) {if (a[i][j] == 2) {haveLight = false;continue;}if (a[i][j] == 1) {haveLight = true;continue;}if (a[i][j] == 3) continue;if (haveLight && a[i][j] == 0) a[i][j] = 3, ans++;}}for (int j = 1; j <= m; j++) {//向上扫haveLight = false;for (int i = n; i >= 1; i--) {if (a[i][j] == 2) {haveLight = false;continue;}if (a[i][j] == 1) {haveLight = true;continue;}if (a[i][j] == 3) continue;if (haveLight && a[i][j] == 0) a[i][j] = 3, ans++;}}cout << ans;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！