読者です 読者をやめる 読者になる 読者になる

TopCoder SRM447 DIV2 500点問題

雑記

 いくら『1日1問TopCoderの問題を解く!』って意気込んでも、1日じゃ解けない問題とかあるよね。


 今回は、自分が初参加したSRM447 DIV2の500点問題を解いてみた。あまりに遅すぎたために点数は150.00点。
 問題を一目見たときに「これRedandBlackみたいにやれば解けるな」と思ったのが間違いだった。様々な条件がこの問題には潜んでいたのだ。


 それを読み解く読解力・・・というよりも英語力の欠如。これは痛い。
 なんにせよ一応解けたので貼っておく。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class KnightsTour {
public:
	char field[12][12];
	int cost[12][12];
	int count;
	static int direx[8];
	static int direy[8];
	
	int costCul(int x, int y) {
		int cnt = 0;
		for(int i = 0; i < 8; i++) {
			if(field[y+direy[i]][x+direx[i]] != '*') cnt++;
		}
		
		return cnt;
	}
	
	class Cell {
	public:
		int x, y, cost;
		Cell(int dx, int dy, int dc) {
			x = dx; y = dy; cost = dc;
		}
		Cell() {};
		bool operator<(const Cell& c) const {
			if(cost == c.cost) {
				if(y == c.y) {
					return x < c.x;
				} else {
					return y < c.y;
				}
			} else {
				return cost < c.cost;
			}
		}
	};
	
	void rec(int x, int y) {
		if(field[y][x] == '*') return;
		Cell cells[8];
		
		cout << x << ":" << y << endl;
		count++;
		field[y][x] = '*';
		for(int i = 0; i < 8; i++) {
			cost[y + direy[i]][x + direx[i]]--;
		}
		
		for(int i = 0; i < 8; i++) {
			if(field[y + direy[i]][x + direx[i]] == '*') {
				Cell c(0, 0, 100);
				cells[i] = c;
			} else {

				Cell c(x + direx[i], y + direy[i], cost[y + direy[i]][x + direx[i]]);
				cells[i] = c;
			}
		}
	
		sort(cells, cells+8);

		rec(cells[0].x, cells[0].y);
	}
	
	int visitedPositions(vector<string> board) {

		int x, y;
		
		for(int i = 0; i < 12; i++) {
			for(int j = 0; j < 12; j++) {
				field[i][j] = '*';
			}
		}
		
		for(int i = 2; i < 10; i++) {
			string str = board[i-2];
			for(int j = 2; j < 10; j++) {
				field[i][j] = str[j-2];
				
				if(field[i][j] == 'K') {
					x = j;
					y = i;
				}
			}
		}
		
		for(int i = 0; i < 12; i++) {
			for(int j = 0; j < 12; j++) {
				cost[i][j] = 9;
			}
		}
		for(int i = 2; i < 10; i++) {
			for(int j = 2; j < 10; j++) {
				cost[i][j] = costCul(j, i);
			}
		}
		
		count = 0;
		rec(x, y);

		return count;
	}
};

int KnightsTour::direx[8] = {2, 1, 2, 1, -2, -1, -2, -1};
int KnightsTour::direy[8] = {1, 2, -1, -2, 1, 2, -1, -2};

 各セルに移動可能な場所の数だけの重みをつけ、その重みの少ない方へ移動するという条件。もし重みが同じならば列番号、行番号を見て小さい方へと移動する・・・。
 このあたりの移動条件が完全に抜けていたため、本番ではまるで違う答えが出ていたのだ。


 それとこの問題ではC++言語に対する理解の低さも浮き彫りにしてくれた。ICPCで使い始めてそのまま使ってきたが、もっと勉強しなきゃスラスラとプログラムを書くのは無理だな。