USACO Wisconsin Squares解題レポート

USER: chen chen [thestor1]
TASK: wissqu
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [2.206 secs, 3504 KB]

All tests OK.
YOUR PROGRAM ('wissqu') WORKED FIRST TIME!  That's fantastic
-- and a rare thing.  Please accept these special automated
congratulations.

この問題は理解するのは難しいですが、簡単にできます.簡単なDFSです.最適化は一切行われていません.また、テストサンプルはこれまで1つしかありませんでした.なぜ最初にDだったのか分かりませんが、そう言った以上、そう書きました.私は自分の机の上で6秒使って、usacoの机械の上で2.2秒しか使いませんでした.

/* 
ID: thestor1 
LANG: C++ 
TASK: wissqu 
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <climits>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>

using namespace std;

int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

class Move
{
public:
	char ch;
	int r, c;
	Move(char ch, int r, int c) : ch(ch), r(r), c(c) {}
};

void DFS(int &cnt, std::vector<string> &square, std::vector<int> &target, int replaced, std::vector<Move> &moves);

void printSquare(std::vector<string> &square)
{
	cout << "[debug]square:" << endl;
	for (int i = 0; i < square.size(); ++i)
	{
		for (int j = 0; j < square[i].size(); ++j)
		{
			cout << square[i][j];
		}
		cout << endl;
	}
}

void fill(int i, int &cnt, std::vector<string> &square, std::vector<int> &target, int replaced, std::vector<Move> &moves)
{
	// cout << "[debug]cnt: " << cnt << ", replaced: " << replaced << endl;
	// printSquare(square);

	target[i]--;

	int nr, nc;
	bool conflict;
	char ch = 'A' + i;
	for (int r = 0; r < square.size(); ++r)
	{
		for (int c = 0; c < square[r].size(); ++c)
		{
			if (square[r][c] == ch || square[r][c] > 'E')
			{
				continue;
			}

			conflict = false;
			for (int d = 0; d < 8; ++d)
			{
				nr = r + dx[d], nc = c + dy[d];
				if (nr < 0 || nr > 3 || nc < 0 || nc > 3)
				{
					continue;
				}
				if (square[nr][nc] == ch || square[nr][nc] == ch - 'A' + 'a')
				{
					conflict = true;
					break;
				}
			}

			if (conflict)
			{
				continue;
			}

			// cout << "[debug]square[" << r << "][" << c << "]:" << square[r][c] << endl;
			char oldchar = square[r][c];
			square[r][c] = ch - 'A' + 'a';

			if (cnt == 0)
			{
				moves.push_back(Move(ch, r + 1, c + 1));
			}
			DFS(cnt, square, target, replaced + 1, moves);
			if (cnt == 0)
			{
				moves.pop_back();
			}
			square[r][c] = oldchar;
		}
	}

	target[i]++;
}

void DFS(int &cnt, std::vector<string> &square, std::vector<int> &target, int replaced, std::vector<Move> &moves)
{
	if (replaced == 16)
	{
		// cout << "[debug]target:" << endl;
		// for (int i = 0; i < target.size(); ++i)
		// {
			// cout << i << ":" << target[i] << endl;
		// }

		// printSquare(square);
		if (cnt == 0)
		{
			ofstream fout("wissqu.out");
			for (int i = 0; i < moves.size(); ++i)
			{
				fout << moves[i].ch << " " << moves[i].r << " " << moves[i].c << endl;
			}
			fout.close();
		}

		cnt++;
		// cout << "[debug]cnt: " << cnt << endl;
		return;
	}

	if (replaced == 0)
	{
		fill(3, cnt, square, target, replaced, moves);
	}
	else
	{
		for (int i = 0; i < target.size(); ++i)
		{
			if (target[i] == 0)
			{
				continue;
			}

			fill(i, cnt, square, target, replaced, moves);
		}
	}
}

int main()
{
	std::vector<string> square;
	ifstream fin("wissqu.in");

	string row;
	for (int r = 0; r < 4; ++r)
	{
		fin >> row;
		square.push_back(row);
	}
	
	fin.close();

	std::vector<int> target(5, 3);
	target[3] = 4;

	int cnt = 0;
	std::vector<Move> moves;
	DFS(cnt, square, target, 0, moves);

	ofstream fout("wissqu.out", std::ofstream::out | std::ofstream::app);
	fout << cnt << endl;
	fout.close();
	return 0;  
}