ZJU 2605 Under Control
Under Control
64-bit integer IO format: %lld Java class name: Main
In a game of Civilization III the area controlled by a city is defined by its culture level. The game proceeds on a rectangular grid. A city occupies one grid square. Each city has aculture level which is a non-negative integer number.
A city with a culture level 0 controls its own square and eight adjacent squares. A city with a culture level 1 additionally controls all squares that share a side with those squares (a total of 9 + 12 = 21 squares). Generally, if a city with a culture level i controls the set A of squares, a city with the same location and a culture level i + 1 would control all these squares and also squares that share a side with at least one square from A.
The picture on the left shows the sets of squares controlled by cities with culture levels of 0, 1 and 2.
The area controlled by the civilization is defined as follows. Consider the total area controlled by all its cities. The civilization area is the smallest set of squares, such that it contains all the squares controlled by some city, and its complement contains no hanging squares. A square x of a set B is called hanging if there is no 2 * 2 square in B that contains square x.
Calculate the total area controlled by a civilization, given the locations of all its cities on a map. You may consider that the map is infinite and that there are no other civilizations.
Input
The input consists of several test cases. In each case, the first line contains an integral number n - the number of the cities of a civilization (1 <= n <= 50). Next n lines describe cities. Each city is described with its integer coordinates (xi, yi) and its culture level ci. Coordinates do not exceed 109 by their absolute value, culture level does not exceed 10. The input ends up with a case where n = 0. Do not proceed this case.
Output
Output the total number of squares controlled by a civilization, each case in a single line.
Sample Input
2 0 0 1 4 -3 0 0
Sample Output
31
NOTE: The squares controlled by the civilization in the example are shown on the right picture. The square marked by a small circle is not controlled by any city, however it belongs to the area controlled by the civilization because otherwise it would be hanging.
Source
Author
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define INF 0x3f3f3f3f 15 #define pii pair<int,int> 16 using namespace std; 17 const int maxn = 100000; 18 const int dir[4][2] = {-1,0,0,1,0,-1,1,0}; 19 pii p[maxn]; 20 set< pii > s; 21 int tot; 22 void solve(int x,int y,int v){ 23 int a = 3 + v*2,k = a>>1; 24 int tx = x - 1; 25 int ty = y + k; 26 for(int i = 0; i < k; ++i){ 27 for(int j = 0; j < 3+2*i; ++j){ 28 pii tmp = make_pair(tx+j,ty); 29 if(s.count(tmp) == 1) continue; 30 s.insert(tmp); 31 p[tot++] = tmp; 32 } 33 --tx; 34 --ty; 35 } 36 tx = x - k; 37 ty = y; 38 for(int i = 0; i < a; ++i){ 39 pii tmp = make_pair(tx+i,ty); 40 if(s.count(tmp) == 1) continue; 41 s.insert(tmp); 42 p[tot++] = tmp; 43 } 44 tx = x - k; 45 ty = y - 1; 46 for(int i = 0; i < k; ++i){ 47 for(int j = 0; j < a; ++j){ 48 pii tmp = make_pair(tx+j,ty); 49 if(s.count(tmp) == 1) continue; 50 s.insert(tmp); 51 p[tot++] = tmp; 52 } 53 a -= 2; 54 tx++; 55 ty--; 56 } 57 } 58 bool iswhite(int x,int y){ 59 pii tmp = make_pair(x,y); 60 return s.count(tmp) == 0; 61 } 62 void go(int x,int y){ 63 bool p1 = iswhite(x-1,y+1); 64 bool p2 = iswhite(x,y+1); 65 bool p3 = iswhite(x+1,y+1); 66 bool p4 = iswhite(x-1,y); 67 bool p5 = iswhite(x+1,y); 68 bool p6 = iswhite(x-1,y-1); 69 bool p7 = iswhite(x,y-1); 70 bool p8 = iswhite(x+1,y-1); 71 72 if(p1 && p2 && p4) return; 73 if(p2 && p3 && p5) return; 74 if(p4 && p6 && p7) return; 75 if(p5 && p7 && p8) return; 76 77 pii tmp = make_pair(x,y); 78 p[tot++] = tmp; 79 s.insert(tmp); 80 } 81 int main(){ 82 int n,x,y,v; 83 while(scanf("%d",&n),n){ 84 s.clear(); 85 for(int i = tot = 0; i < n; ++i){ 86 scanf("%d %d %d",&x,&y,&v); 87 solve(x,y,v); 88 } 89 for(int i = 0; i < tot; ++i){ 90 for(int j = 0; j < 4; ++j){ 91 int tx = p[i].first + dir[j][0]; 92 int ty = p[i].second + dir[j][1]; 93 if(iswhite(tx,ty)) go(tx,ty); 94 } 95 } 96 printf("%d\n",s.size()); 97 } 98 return 0; 99 }
相关文章
- 微信小程序 - bindcontroltap和control的关系(map)
- HDU 4289 Control
- Origin null is not allowed by Access-Control-Allow-Origin
- High waits on control file sequential read
- 写给后端程序员的HTTP缓存原理介绍--怎样决定一个资源的Cache-Control策略呢
- 【转载】 tensorflow中的batch_norm以及tf.control_dependencies和tf.GraphKeys.UPDATE_OPS的探究
- 新版Windows 10曝光全新的Control Center
- rhino(犀牛) --- color control
- 初步认识pg_control文件之一
- Inversion of Control Containers and the Dependency Injection pattern--Martin Fowler
- 一款开源且功能强大的C#甘特图控件.NET Winforms Gantt Chart Control
- 一款开源且功能强大的C#甘特图控件.NET Winforms Gantt Chart Control
- json检查语法时报错 (json.decoder.JSONDecodeError: Invalid control character at: line 1 column)