제출 #200651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
200651		tincamatei	바이러스 (JOI19_virus)	C++14	6 / 100	1119 ms	262148 KiB

virus

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 800;

int U[1+MAX_N+1][1+MAX_N+1];
int timestamp, nr = 0;
int viz[1+MAX_N+1][1+MAX_N+1];

int force[1<<4];

int chToDir[128];
char dirToCh[4 + 1] = "SENW";
int dl[] = {1, 0, -1, 0};
int dc[] = {0, 1,  0,-1};

void init() {
	for(int i = 0; i < 4; ++i)
		chToDir[dirToCh[i]] = i;
}


bool getInfected(int l, int c) {
	int mask = 0;
	for(int i = 0; i < 4; ++i) {
		int ln = l + dl[i];
		int cn = c + dc[i];
		if(viz[ln][cn] == timestamp)
			mask = mask | (1 << i); // Mark the opposite direction
	}

	return U[l][c] != 0 && U[l][c] <= force[mask];
}

vector<pair<int, int> > comp;

void dfs(int l, int c) {
	viz[l][c] = timestamp;
	++nr;

	comp.push_back({l, c});

	for(int i = 0; i < 4; ++i) {
		int ln = l + dl[i];
		int cn = c + dc[i];
		if(timestamp > viz[ln][cn] && getInfected(ln, cn))
			dfs(ln, cn);
	}
}

void clearDfs() {
	for(auto it: comp)
		viz[it.first][it.second] = false;
	comp.clear();
}

int main() {
	int M, R, C;
	string D;

	init();

	cin >> M >> R >> C >> D;
	for(int i = 1; i <= R; ++i)
		for(int j = 1; j <= C; ++j)
			cin >> U[i][j];

	for(int mask = 1; mask < (1 << 4); ++mask) {
		int cnt = 0, best = 0;
		for(int _i = 0; _i < 2 * M; ++_i) {
			int i = _i % M;

			if(mask & (1 << chToDir[D[i]]))
				++cnt;
			else
				cnt = 0;

			best = max(best, cnt);
		}

		if(best >= M)
			best = 100001;
		force[mask] = best;
	}

	int rez = R * C + 1, cntRez = 0;
	for(int i = 1; i <= R; ++i)
		for(int j = 1; j <= C; ++j) {
			if(U[i][j] != 0) {
				++timestamp;
				nr = 0;
				dfs(i, j);
				if(nr < rez) {
					rez = nr;
					cntRez = 1;
				} else if(nr == rez)
					cntRez += 1;
			}
		}

	printf("%d\n%d", rez, cntRez);

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

virus.cpp: In function 'void init()':
virus.cpp:20:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   chToDir[dirToCh[i]] = i;
                     ^
virus.cpp: In function 'int main()':
virus.cpp:74:32: warning: array subscript has type 'char' [-Wchar-subscripts]
    if(mask & (1 << chToDir[D[i]]))
                                ^

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