제출 #489521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489521		8e7	Virus Experiment (JOI19_virus)	C++17	0 / 100	6 ms	972 KiB

virus

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
void debug(){cout << endl;}
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 805
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
bool poss[maxn][maxn][16];
bool done[maxn][maxn], vis[maxn][maxn], col[maxn][maxn];
int ans[maxn][maxn];
int u[maxn][maxn], ds[100005], dt[maxn];
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // NESW
int r, c;
inline bool in(int x, int y){return x >= 0 && x < r && y >= 0 && y < c;}
bool con(int x, int y) {
	int mask = 0;
	for (int i = 0;i < 4;i++) {
		int dx = x + dir[i][0], dy = y + dir[i][1];
		if (in(dx, dy)) mask += col[dx][dy] ? (1<<i) : 0;
	}
	return poss[x][y][mask];
}
int pnt = 0;
void dfs(int x, int y) {
	col[x][y] = 1;
	pnt++;
	for (int i = 0;i < 4;i++) {
		int dx = x + dir[i][0], dy = y + dir[i][1];
		if (!in(dx, dy)) continue;
		if (con(dx, dy) && !col[dx][dy]) {
			dfs(dx, dy);
		}
	}
}
int main() {
	io
	int m;
	cin >> m >> r >> c;
	string D;
	cin >> D;
	for (int i = 0;i < m;i++) ds[i] = (D[i] == 'N' ? 0 : (D[i] == 'E' ? 1 : (D[i] == 'S' ? 2 : 3)));
	for (int i = 0;i < r;i++) {
		for (int j = 0;j < c;j++) cin >> u[i][j];
	}
	for (int ti = 0;ti < 16;ti++) {
		int ma = 0, cur = 0, tot = 0, pref = 0, suf = 0;
		for (int i = 0;i < m;i++) {
			if (ti & (1<<ds[i])) {
				dt[i] = 1;
			} else {
				ma = max(ma, cur);
				cur = 0;
				dt[i] = 0;
			}
			cur += dt[i];
			tot += dt[i];
		}
		if (tot == m) {
			ma = 1<<30;	
		} else {
			for (int i = 0;i < m;i++) {
				if (!dt[i]) {
					pref = i;
					break;
				}
			}
			for (int i = m - 1;i >= 0;i--) {
				if (!dt[i]) {
					suf = m - 1 - i;
					break;
				}
			}
			ma = max(ma, pref + suf);
		}
		//debug(ma);
		for (int i = 0;i < r;i++) {
			for (int j = 0;j < c;j++) {
				poss[i][j][ti] = u[i][j] <= ma;
				if (u[i][j] == 0) poss[i][j][ti] = 0;
			}
		}
	}
	int out = 1<<30, outn = 0;
	for (int i = 0;i < r;i++) {
		for (int j = 0;j < c;j++) {
			pnt = 0;	
			if (u[i][j]) {
				dfs(i, j);
				if (pnt < out) {
					out = pnt;
					outn = 1;
				} else if (pnt == out) outn++;
				out = min(out, pnt);
				pnt = 0;
				for (int x = 0;x < r;x++) {
					for (int y = 0;y < c;y++) col[x][y] = 0;
				}
			}
		}
	}
	cout << out << "\n" << outn << "\n";
}
/*

6 3 4
SWNEES
2 1 1 2
1 0 1 3
1 1 2 2
*/

• Subtask 1: 0 / 14
• Subtask 2: 0 / 6
• Subtask 3: 0 / 80