18242, silver 5

18242번: 네모네모 시력검사

문제

• $n\times m(5\leq n,\ m \leq 100)$ 격자판에 한 변만 중심이 뚫린 직사각형이 있다. 뚤린 변은 어느쪽인가?

 

$O(nm)$

격자판을 위쪽부터 아래쪽으로, 왼쪽에서 아래쪽으로 탐색을 하면서 # 이 나올 때 좌표를 벡터에 저장한다
그러면 벡터의 제일 처음과 끝 원소는 아래 그림과 같다

※ $x-y$ 좌표계가 아니라 행렬이라는 것에 주의할 것!

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
char d [101][101] {};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    vector<pair<int, int> > v;
    for(int r = 0; r < n; r++) {
        cin >> d[r];
        for(int c = 0; c < m; c++){
            if(d[r][c] == '#') v.emplace_back(r, c);
        }
    }
 
    int r1, c1, r2, c2;
    tie(r1, c1) = v.front();
    tie(r2, c2) = v.back();
 
    if(d[r1][(c1+c2)/2] != '#') cout << "UP" << endl;
    else if(d[r2][(c1+c2)/2] != '#') cout << "DOWN" << endl;
    else if(d[(r1+r2)/2][c1] != '#') cout << "LEFT" << endl;
    else cout << "RIGHT" << endl;
 
    return 0;
}