题面：

传送门

题目描述：

要求用十字星星来画题目给出的“星”图。如果不能用十字星星来画“星”图，输出-1；如果能，则输出要在图的哪个位置画相应大小的十字星图。

题目分析：

这道题纯属模拟题，按照要求画就好了。我的画法：根据题目的“星”图用十字星图在另一个二维数组画“星”图。拿第一个样例来说：当遍历到第一颗星星，我就会检查是否能用十字星星去按题目给出的“星图”填充：

显然，第一个星星不能用十字星星去画图。那么这里哪些星星可以画呢？我们可以看出来这个星星可以画：

在这里我们在另外一个二维数组画大小为1的十字星星：

然后我们又发现了可以画一个大小为3的十字星星：

这时，我们就成功用十字星星画出原来的星图。检查是否成功，直接把原星图和自己画的星图（二维数组）遍历一遍比较是否相等就行了。但是，在画的过程中，我们每画一次星图就要检查一遍吗？其实是不需要的。因为我们也可以多“画”，比如像这样：

当我们从上到下，从左到右遍历一遍，画到这个星星的时候：

显然，还没画这个位置的十字星图时，自己画的星图之前就已经画好了（之前在第2行第5列画大小为1的十字星星，在第3行第4列画大小为1的十字星星，在第3行第5列画大小为3的十字星星，在第3行第6列画大小为1的十字星星）。但是题目允许“覆盖”，也就是我在这个位置画大小为1的十字星星也不会错，那么我们就在这里画个十字星星，把这个也输出到结果。这样做的好处是：遍历完原星图所有星星后，只需要检查一遍就可以知道是否能用十字星星画出原星图。要注意的是，画十字星星要画：能画的最大大小。

AC代码：

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <algorithm>

 5 #include <stack>

 6 #include <queue>

 7 using namespace std;

 8 const int maxn = 105;

 9 char a[maxn][maxn];     //原星图

10 int point[maxn][maxn];  //自己画的图

11 int dr[4] = {-1, 1, 0, 0}, dc[4] = {0,0,-1,1};  //上下左右

12 int n, m;

13

14 struct node{

15     int x;

16     int y;

17     int type;

18 };

19

20 queue<node> q;   //用队列保存结果

21

22 int check(int r, int c){   //检查是否能画

23     int flag;

24     int r1, c1;

25     node temp;

26     temp.type = 0;

27     for(int sizes = 1; sizes <= 50; sizes++){

28         flag = 1;

29         for(int i = 0; i < 4; i++){

30             r1 = r + dr[i]*sizes;

31             c1 = c + dc[i]*sizes;

32             if(r1 >= 0 || r1 < n || c1 >= 0 || c1 < m){

33                 if(a[r1][c1] != '*') flag = 0;  //如果上下左右不是星号就不能画

34             }

35             else {flag = 0; break;}

36         }

37

38         if(flag){   //保存能画的最大十字星星

39             point[r][c] = 1;

40             for(int i = 0; i < 4; i++){

41                 r1 = r + dr[i]*sizes;

42                 c1 = c + dc[i]*sizes;

43                 point[r1][c1] = 1;

44             }

45             temp.type = sizes;

46             temp.x = r;

47             temp.y = c;

48         }

49         else break;

50     }

51     if(temp.type) {q.push(temp);return 1;} //把结果加入队列

52     return 0;

53 }

54

55 bool check2(){   //检查画出来的是否和原星图一致

56     for(int i = 0; i < n; i++){

57         for(int j = 0; j < m; j++){

58             if(a[i][j] == '*'){

59                 if(point[i][j]==0) return false;

60             }

61         }

62     }

63     return true;

64 }

65

66 int main(){

67     memset(a, 0, sizeof(a));

68     memset(point, 0, sizeof(point));

69     cin >> n >> m;

70     for(int i = 0; i < n; i++) cin >> a[i];

71

72     int cnt = 0;  //计数

73     node temp;

74     for(int i = 0; i < n; i++){

75         for(int j = 0; j < m; j++){

76             if(a[i][j] == '*'){

77                 if(check(i, j)){  //符合条件就画

78                     cnt++;

79                 }

80             }

81         }

82     }

83

84     if(check2()){

85         printf("%d\n", cnt);

86         while(!q.empty()){

87             temp = q.front(); q.pop();

88             printf("%d %d %d\n", temp.x+1, temp.y+1, temp.type);

89         }

90     }

91     else cout << -1 << endl;

92     return 0;

93 }

巴特西

Codeforces 1015E1 Stars Drawing (Easy Edition)

题面：

题目描述：

题目分析：

最新文章

热门文章