Submission #169964

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <iterator>
#include <algorithm>
#include <functional>
#include <bitset>
#include <string>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

unsigned W, H, N;

typedef std::vector<bool>     FieldRow;
typedef std::vector<FieldRow> Field;

typedef std::pair<int, int> Point2D;
std::vector<Point2D> M;

unsigned count(const std::vector<unsigned>& v) {
	Field field = Field(H);
	for(unsigned h=0; h<H; ++h) {
		field[h] = FieldRow(W);
		std::fill(field[h].begin(), field[h].end(), false);
	}
	
	for(unsigned n=0; n<N; ++n) {
		Point2D p = M[ v[n] ];
		
		field[p.second][p.first] = true;
		for(int x=p.first+1, y=p.second; (x< W && !field[y][x]); ++x) field[y][x]=true;
		for(int x=p.first-1, y=p.second; (x>=0 && !field[y][x]); --x) field[y][x]=true;
		for(int x=p.first, y=p.second+1; (y< H && !field[y][x]); ++y) field[y][x]=true;
		for(int x=p.first, y=p.second-1; (y>=0 && !field[y][x]); --y) field[y][x]=true;
	}
	
	unsigned c = 0;
	for(unsigned y=0; y<H; ++y) {
		for(unsigned x=0; x<W; ++x) {
			if(field[y][x]) ++c;
		}
	}
	return c;
}

int main(void) {
	std::cin >> W >> H >> N;
	
	for(unsigned n=0; n<N; ++n) {
		unsigned x, y;
		std::cin >> x >> y;
		M.push_back( Point2D(x-1, y-1) );
	}
	
	std::vector<unsigned> array(N);
	for(unsigned n=0; n<N; ++n) array[n] = n;
	
	unsigned max = 0;
	do {
		unsigned ret = count(array);
		if(ret > max) max = ret;
	} while( std::next_permutation(array.begin(), array.end()) );
	
	std::cout << max << std::endl;
	
	return 0;
}

Submission Info

Judge Result