MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 201 - Square
AOAPC II

UVaOJ 201 - Square

Chai
2021-11-24 0:00:00在线评测阅读 318

问题描述

p201

原题链接:UVaOJ 201 - Square

相关说明:本题为《算法竞赛入门经典(第2版)》习题 4-2

解法一:模拟

遍历每个点进行判断,看以这个点 [x][y] 作为左上角可以得到多少个正方形:对于大小为 l 的正方形,只需要满足三个起点(左上、左下、右上)能够延伸出长度为 l 的边就行了。

C++
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
#include <bits/stdc++.h>
 
using namespace std;
 
int h[10][10], v[10][10], s[10];
 
bool has_h(int x, int y, int l) {
  for (int p = 0; p < l; ++p)
    if (h[x][y + p] != 1) return false;
  return true;
}
 
bool has_v(int x, int y, int l) {
  for (int p = 0; p < l; ++p)
    if (v[x + p][y] != 1) return false;
  return true;
}
 
void count_square(int x, int y, int max_l) {
  for (int l = 1; l <= max_l; ++l) {
    if (has_h(x, y, l) && has_h(x + l, y, l) && has_v(x, y, l) &&
        has_v(x, y + l, l))
      s[l] += 1;
  }
}
 
int main() {
  int n, m, tmp, x, y, problem_num = 0;
  string dir;
  while (cin >> n) {
    if (problem_num)
      cout << endl << "**********************************" << endl << endl;
    cout << "Problem #" << ++problem_num << endl << endl;
    memset(h, 0, sizeof(h));
    memset(v, 0, sizeof(v));
    memset(s, 0, sizeof(s));
 
    cin >> m;
    while (m--) {
      cin >> dir >> x >> y;
      if (dir == "H") h[x][y] = 1;
      if (dir == "V") v[y][x] = 1;
    }
 
    for (int i = 1; i < n; ++i)
      for (int j = 1; j < n; ++j) count_square(i, j, n - max(i, j));
 
    int total_num = 0;
    for (int i = 1; i < n; ++i) {
      if (s[i]) cout << s[i] << " square (s) of size " << i << endl;
      total_num += s[i];
    }
    if (!total_num) cout << "No completed squares can be found." << endl;
  }
  return 0;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz