[swea 5644] 무선 충전

분류 : 구현

 

요구사항

충전량을 최대로하여 이동하기

 

풀이

map의 범위도 작고 bc의 갯수도 작고 이동 횟수도 작다

100초동안 2명의 사람이 bc에 방문하는 모든 경우의 수를 계산하면 된다

이렇게 안풀면 예외 처리해줘야 할게 너무 많다

 

밧데리 충전 -> ans 갱신 -> 이동 순으로 구현하면 된다.

 

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;
struct go {
	int c;
	int r;
	int cap;
	int power;
};
int m, a;
vector<int> v1;
vector<int> v2;
vector<go> bc;
int dr[5] = { 0,-1,0,1,0 };
int dc[5] = { 0, 0,1,0,-1 };
int map[14][14];
int ans = 0;
void solve() {
	int s1 = 1;
	int c1 = 1;
	int s2 = 10;
	int c2 = 10;
	map[s1][c1] = 1;
	map[s2][c2] = 2;
	int bcsize = bc.size();
	for (int i = 0; i < m+1; i++) {
		
		//j는 1 k는 2번
		int temp = 0;
		for (int j = 0; j < bcsize; j++) {
			for (int k = 0; k < bcsize; k++) {
				int bc1r = bc[j].r;
				int bc1c = bc[j].c;
				int bc2r = bc[k].r;
				int bc2c = bc[k].c;
				bool flag1 = false;
				bool flag2 = false;
				int dist1 = abs(s1 - bc1r) + abs(c1 - bc1c);
				int dist2 = abs(s2 - bc2r) + abs(c2 - bc2c);

				if (dist1 <= bc[j].cap) {
					flag1 = true;
				}
				if (dist2 <= bc[k].cap) {
					flag2 = true;
				}
				if (flag1 == true && flag2 == true) {
					if (k == j) {
						temp = max(temp, bc[j].power);
					}
					else {
						int temppower = bc[j].power + bc[k].power;
						temp = max(temp, temppower);
					}
				}
				if (flag1 == true && flag2 == false) {
					int temppower = bc[j].power;
					temp = max(temp, temppower);
				}
				if (flag1 == false && flag2 == true) {
					int temppower = bc[k].power;
					temp = max(temp, temppower);
				}
				

				
			}
		}
		ans += temp;
		//cout << i << " " << temp << endl;
		if (i == m)
			break;
		s1 = s1 + dr[v1[i]];
		c1 = c1 + dc[v1[i]];
		s2 = s2 + dr[v2[i]];
		c2 = c2 + dc[v2[i]];
	}
	
}
int main() {
	int t;
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		ans = 0;
		v1.clear();
		v2.clear();
		bc.clear();
		scanf("%d%d", &m, &a);
		for (int j = 0; j < 2; j++) {
			for (int i = 0; i < m; i++) {
				int x;
				scanf("%d", &x);
				if (j == 0) {
					v1.push_back(x);
				}
				if (j == 1) {
					v2.push_back(x);
				}
			}
		}
		for (int i = 0; i < a; i++) {
			int x, y, z, w;
			scanf("%d%d%d%d", &x, &y, &z, &w);
			bc.push_back({ x,y,z,w });
			//map[y][x] = 5;
		}
		solve();
		printf("#%d %d\n", tc, ans);

	}
}