题目：有m*n的矩形，每个方块默认为白色，现给k个方块图上黑色，问有多少连续的num*1或1*num的长方形。如果一个1*1的方块周围没有白色方块，那么这个方块也包含在答案里面。
解析：行列遍历。对行和列分别进行查找，对行和列查找过程中单独成一个方块的坐标分别记录在两个集合中，最终只需要在结果上加上两个集合的交集中元素的个数。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
#include<iostream> #include<algorithm> #include<iterator> #include<set> using namespace std; struct Point { int x, y; bool operator< (const Point & a)const { if (this->x == a.x)return this->y < a.y; return this->x < a.x; } }point[60000]; int fx(Point& a, Point& b) { if (a.x == b.x)return a.y < b.y; return a.x < b.x; } int fy(Point& a, Point& b) { if (a.y == b.y)return a.x < b.x; return a.y < b.y; } void insert(set<Point>& a, int x, int y) { Point tempPoint; tempPoint.x = x; tempPoint.y = y; a.insert(tempPoint); } int main() { int m, n, k, ans = 0; cin >> n >> m >> k; set<Point> A; set<Point> B; set<Point> C; for (int i = 0; i < k; i++)cin >> point[i].x >> point[i].y; int now = 0, row = 0, col = 0; if (n == 1) { sort(point, point + k, fx); if (point[0].y == 1) ans++; for (int i = 1; i < k; i++) { if (point[i].y - point[i - 1].y == 1) ans++; } if (point[k - 1].y == m) ans++; cout << k + 1 - ans; return 0; } if (m == 1) { sort(point, point + k, fy); if (point[0].x == 1) ans++; for (int i = 1; i < k; i++) { if (point[i].x - point[i - 1].x == 1) ans++; } if (point[k - 1].x == n) ans++; cout << k + 1 - ans; return 0; } sort(point, point + k, fx); while (row < n) { if (point[now].x != row + 1) { ans++; row++; continue; } if (point[now].y == 2) insert(A, point[now].x, 1); else if (point[now].y > 2) ans++; now++; while (now < k) { if (point[now].x == point[now - 1].x) { if (point[now].y - point[now - 1].y == 2) insert(A, point[now].x, point[now].y - 1); else if (point[now].y - point[now - 1].y > 2) ans++; } else { break; } now++; } if (point[now - 1].y == m - 1) insert(A, point[now - 1].x, m); else if (point[now - 1].y < m - 1) ans++; row++; } sort(point, point + k, fy); now = 0; while (col < m) { if (point[now].y != col + 1) { ans++; col++; continue; } if (point[now].x == 2) insert(B, 1, point[now].y); else if (point[now].x > 2) ans++; now++; while (now < k) { if (point[now].y == point[now - 1].y) { if (point[now].x - point[now - 1].x == 2) insert(B, point[now].x - 1, point[now].y); else if (point[now].x - point[now - 1].x > 2) ans++; } else { break; } now++; } if (point[now - 1].x == n - 1) insert(B, n, point[now - 1].y); else if (point[now - 1].x < n - 1) ans++; col++; } set_intersection(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin())); ans += C.size(); cout << ans << endl; } |
浙公网安备 33010902002953号