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

tookunn’s diary

主に競技プログラミング関係

AOJ 2311 Dessert Witch

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2311
なんかオセロっぽいやつで、問題文で指定された手順でオセロの最終盤面を出力する
実装問題です。
普通に面倒でした。デバッグしまくってやっと通しました。

解法

問題文で指定されている通りに実装するだけだと思いますが、僕の場合は一気に書いて「通るでしょ」みたいな感じでやったらハマりまくってかなり時間掛かりました。
やっぱり少しずつデバッグして確かめながら書いた方が良かったかもしれません。

ソースコード

#include<iostream>
#include<string>
using namespace std;

string table[8];
int dx[] = {0,1,1,1,0,-1,-1,-1};
int dy[] = {-1,-1,0,1,1,1,0,-1};
bool isInRange(int nx,int ny)
{
	if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8)return false;
	return true;
}

int isPut(int x,int y,char putCookie)
{
	int maxReverse = 0;
	for (int i = 0; i < 8; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		
		int count = 0;
		while (isInRange(nx, ny) && table[ny][nx] != putCookie && table[ny][nx] != '.')
		{
			if (putCookie == table[ny][nx])break;
			count++;
			nx += dx[i];
			ny += dy[i];
		}

		if (isInRange(nx,ny) && table[ny][nx] == putCookie)
		{
			maxReverse += count;
		}
	}
	return maxReverse;
}
void reversing(int px, int py,char putCookie)
{
	//一番最初に置くクッキー
	table[py][px] = putCookie;

	char targetCookie;
	if (putCookie == 'o')targetCookie = 'x';
	else targetCookie = 'o';

	for (int i = 0; i < 8; i++)
	{
		int ny = py + dy[i];
		int nx = px + dx[i];
		bool isPut = false;

		int canReverseCount = 0;
		while (isInRange(nx,ny) && table[ny][nx] != '.')
		{
			if (putCookie == table[ny][nx])
			{
				isPut = true;
				break;
			}
			canReverseCount++;
			ny += dy[i];
			nx += dx[i];
		}

		if (isPut)
		{
			int nextY = py + dy[i];
			int nextX = px + dx[i];
			for (int j = 0; j < canReverseCount; j++)
			{
				table[nextY][nextX] = putCookie;
				nextY = nextY + dy[i];
				nextX= nextX + dx[i];
			}
		}
	}
}
//置けた場合trueを返す
bool searchPutPos(char putCookie,int turn)
{
	int maxReverse = 0;
	int putX = 0;
	int putY = 0;
	if (turn % 2 == 0)//巴マミのターン
	{
		for (int i = 0; i < 8; i++)
		{
			for (int j = 0; j < 8; j++)
			{
				if (table[i][j] != '.')continue;
				//自分のクッキーを置いた場合に
				//他のプレイヤーのクッキーを反転させることができる数が返される
				int reverseNumber = isPut(j, i, putCookie);
				if (reverseNumber == 0)continue;
				if (maxReverse < reverseNumber)
				{
					maxReverse = reverseNumber;
					putX = j;
					putY = i;
				}
			}
		}
	}
	else//お菓子の魔女のターン
	{
		for (int i = 7; i >= 0; i--)
		{
			for (int j = 7; j >= 0; j--)
			{
				if (table[i][j] != '.')continue;
				int reverseNumber = isPut(j, i, putCookie);
				if (reverseNumber == 0)continue;
				if (maxReverse < reverseNumber)
				{
					maxReverse = reverseNumber;
					putX = j;
					putY = i;
				}
			}
		}
	}
	//反転させることができない場合
	if (maxReverse == 0)return false;

	//反転処理
	reversing(putX,putY,putCookie);

	//cout << putX << " "<<putY << endl;
	return true;
}
int main()
{
	for (int i = 0; i < 8; i++)
	{
		cin >> table[i];
	}
	bool pfind = true;
	for (int turn = 0;;turn++)
	{
		char putCookie = '-';//初期値は適当な値を入れる
		if (turn % 2 == 1)//お菓子の魔女のターン
		{
			putCookie = 'x';//チーズクッキー
		}
		else//巴マミのターン
		{
			putCookie = 'o';//チョコレートクッキー
		}
		//クッキーがおける場所が見つかったか否かのboolを返す
		bool find = searchPutPos(putCookie, turn);

		if (!find && !pfind)//前ターンのプレイヤーも置けていなかったらゲーム終了
		{
			break;
		}
		pfind = find;
		//cout << turn << endl;
	}

	for (int i = 0; i < 8; i++)
	{
		cout << table[i] << endl;
	}
	return 0;
}

感想

日本語の問題文で良かった。