답안 #736141

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
736141 2023-05-05T09:03:04 Z marvinthang Zoo (COCI19_zoo) C++17
110 / 110
156 ms 39092 KB
/*************************************
*    author: marvinthang             *
*    created: 05.08.2022 11:16:36`    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                 div  ___div
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define             FULL(i)  (MASK(i) - 1)
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

template <class T>             scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T>            print_op(vector <T>)  { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V>   scan_op(pair <U, V>)  { return in >> u.fi >> u.se; }
template <class U, class V>  print_op(pair <U, V>)  { return out << '(' << u.fi << ", " << u.se << ')'; }

const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
const int MAX = 1002;

int numRow, numCol, numComp, inComp[MAX][MAX];
char grid[MAX][MAX];

bool inside(int x, int y) { return 1 <= x && x <= numRow && 1 <= y && y <= numCol && grid[x][y] != '*'; }

void init(void) {
	cin >> numRow >> numCol;
	for (int i = 1; i <= numRow; ++i)
		for (int j = 1; j <= numCol; ++j)
			cin >> grid[i][j];
}

void bfs(int s, int t) {
	++numComp;
	inComp[s][t] = numComp;
	queue <pair <int, int>> q;
	q.push(make_pair(s, t));
	while (!q.empty()) {
		auto [u, v] = q.front(); q.pop();
		for (int d = 0; d < 4; ++d) {
			int x = u + dir[d];
			int y = v + dir[d + 1];
			if (inside(x, y) && !inComp[x][y] && grid[x][y] == grid[s][t]) {
				inComp[x][y] = numComp;
				q.push(make_pair(x, y));
			}
		}
	}
}

vector <int> adj[MAX * MAX];
int dist[MAX * MAX];

void process(void) {
	for (int i = 1; i <= numRow; ++i)
		for (int j = 1; j <= numCol; ++j)
			if (inside(i, j) && !inComp[i][j]) bfs(i, j);
	for (int x = 1; x <= numRow; ++x) for (int y = 1; y <= numCol; ++y) if (inside(x, y)) for (int d = 0; d < 4; ++d) {
		int u = x + dir[d];
		int v = y + dir[d + 1];
		if (!inside(u, v) || inComp[x][y] == inComp[u][v]) continue;
		adj[inComp[x][y]].push_back(inComp[u][v]);
	}
	for (int i = 1; i <= numComp; ++i) {
		sort(adj[i].begin(), adj[i].end());
		adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
	}
	queue <int> q;
	dist[1] = 1;
	q.push(1);
	while (true) {
		int u = q.front(); q.pop();
		for (int v: adj[u]) if (!dist[v]) {
			dist[v] = dist[u] + 1;
			q.push(v);
		}
		if (q.empty()) return void(cout << dist[u] << '\n');
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("coci1920_r1_zoo");
	init();
	process();
	// cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

zoo.cpp: In function 'int main()':
zoo.cpp:22:69: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoo.cpp:95:2: note: in expansion of macro 'file'
   95 |  file("coci1920_r1_zoo");
      |  ^~~~
zoo.cpp:22:103: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
zoo.cpp:95:2: note: in expansion of macro 'file'
   95 |  file("coci1920_r1_zoo");
      |  ^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 12 ms 23920 KB Output is correct
3 Correct 13 ms 24020 KB Output is correct
4 Correct 14 ms 24120 KB Output is correct
5 Correct 14 ms 24404 KB Output is correct
6 Correct 14 ms 24404 KB Output is correct
7 Correct 14 ms 24440 KB Output is correct
8 Correct 15 ms 24404 KB Output is correct
9 Correct 13 ms 24404 KB Output is correct
10 Correct 14 ms 24440 KB Output is correct
11 Correct 15 ms 24404 KB Output is correct
12 Correct 15 ms 24404 KB Output is correct
13 Correct 14 ms 24264 KB Output is correct
14 Correct 18 ms 24404 KB Output is correct
15 Correct 14 ms 24304 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 12 ms 23920 KB Output is correct
3 Correct 13 ms 24020 KB Output is correct
4 Correct 14 ms 24120 KB Output is correct
5 Correct 14 ms 24404 KB Output is correct
6 Correct 14 ms 24404 KB Output is correct
7 Correct 14 ms 24440 KB Output is correct
8 Correct 15 ms 24404 KB Output is correct
9 Correct 13 ms 24404 KB Output is correct
10 Correct 14 ms 24440 KB Output is correct
11 Correct 15 ms 24404 KB Output is correct
12 Correct 15 ms 24404 KB Output is correct
13 Correct 14 ms 24264 KB Output is correct
14 Correct 18 ms 24404 KB Output is correct
15 Correct 14 ms 24304 KB Output is correct
16 Correct 35 ms 29780 KB Output is correct
17 Correct 33 ms 29816 KB Output is correct
18 Correct 33 ms 29972 KB Output is correct
19 Correct 38 ms 29888 KB Output is correct
20 Correct 34 ms 29772 KB Output is correct
21 Correct 145 ms 38444 KB Output is correct
22 Correct 144 ms 38344 KB Output is correct
23 Correct 145 ms 38512 KB Output is correct
24 Correct 155 ms 39092 KB Output is correct
25 Correct 156 ms 38916 KB Output is correct
26 Correct 141 ms 38744 KB Output is correct
27 Correct 138 ms 38368 KB Output is correct
28 Correct 140 ms 38296 KB Output is correct
29 Correct 146 ms 38988 KB Output is correct
30 Correct 144 ms 38784 KB Output is correct