CF Round #713 B - Almost Rectangle


Tags:cpcodeforcesdiv3just_dogeometry

問題

https://codeforces.com/contest/1512/problem/B

問題文

n×nn \times n のマス目が与えられる。
2 つのマスが * で塗られている。
さらに 2 つのマスを選んで、長方形の角になるようにしてね。
複数の解がある場合は、どれでもよい。

制約

  • 1t4001 \le t \le 400
  • 2n4002 \le n \le 400
  • nn の総和は 400400 を超えない
  • * はちょうど 2 つ
  • 解があることは保証される

サンプル

6
4
..*.
....
*...
....
2
*.
.*
2
.*
.*
3
*.*
...
...
5
.....
..*..
.....
.*...
.....
4
....
....
*...
*...
*.*.
....
*.*.
....

**
**

**
**

*.*
*.*
...

.....
.**..
.....
.**..
.....

....
....
**..
**..

考察

やるだけ。
2 つの点を見つける。同じ行/列にあるかチェックする。いい感じに 2 点を加える。

コード

https://codeforces.com/contest/1512/submission/125538680

void solve() {
  int n;
  cin >> n;
  vector Grid(n, vector<bool>(n, false));
  pair<int, int> a, b;
  bool found1 = false;
  rep(i, n) {
    string s;
    cin >> s;
    rep(j, n) {
      if (s[j] == '*') {
        Grid[i][j] = true;
        if (!found1) {
          a = { i, j };
          found1 = true;
        }
        else {
          b = { i, j };
        }
      }
    }
  }
  if (a.first == b.first && a.first != n - 1) {
    Grid[a.first + 1][a.second] = true;
    Grid[b.first + 1][b.second] = true;
  }
  else if (a.first == b.first) {
    Grid[a.first - 1][a.second] = true;
    Grid[b.first - 1][b.second] = true;
  }
  else if (a.second == b.second && a.second != n - 1) {
    Grid[a.first][a.second + 1] = true;
    Grid[b.first][a.second + 1] = true;
  }
  else if (a.second == b.second) {
    Grid[a.first][a.second - 1] = true;
    Grid[b.first][a.second - 1] = true;
  }
  else {
    Grid[a.first][b.second] = true;
    Grid[b.first][a.second] = true;
  }

  rep(i, n) {
    rep(j, n) {
      cout << (Grid[i][j] ? "*" : ".");
    }
    cout << endl;
  }
}