[AlgorithmQuiz/MineSweeper] [Cee] --[destine], 2004-09-14

{{{#!cplusplus

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <stdlib.h>
#include <strstream>

using namespace std;

class solution{
public:
	solution()
	{
		m_nX = 0;
		m_nY = 0;
		m_strData.erase();
	}

	~solution()
	{
	}

	void setX(int x)
	{
		m_nX = x;
	}

	void setY( int y )
	{
		m_nY = y;
	}

	void setData( string data )
	{
		m_strData = data;
	}

	void solve()
	{
		if ( m_strData.length() < m_nX * m_nY - 1 )
			return;
		
		// clear solution
		m_solution.clear();
		for( int i = 0; i < m_nX; i++ )
			for( int j = 0; j < m_nY; j++ )
				m_solution.push_back(0);


		// calculate
		int nIndex;
		for( int y = 0; y < m_nY; y ++ )
		{
			for ( int x = 0; x < m_nX; x ++ )
			{
				nIndex = y * m_nX + x;
				if( m_strData.at( nIndex ) == '*' )
				{
					addMine( x, y );	
				}
			}
		}
	}

	string getResult()
	{
		int nIndex;

		strstream result;
		
		for ( int y = 0; y < m_nY; y++ )
		{
			for ( int x = 0; x < m_nX; x ++ )
			{
				nIndex = y * m_nX + x;
				if ( m_solution[nIndex] == -1 )
					result << '*';
				else
					result << m_solution[nIndex];
			}
			result<<'\n';
		}
		string strResult;
		getline( result, strResult, ' ' );
		return strResult + "\n";
	}

protected:
	void addMine( int x, int y )
	{
		m_solution[y*m_nX+x] = -1;
		for( int i = x - 1; i <= x + 1; i ++ )
			for ( int j = y - 1; j <= y + 1; j ++ )
				addHint( i, j );
	}

	void addHint( int x, int y )
	{
		if ( x < 0 || y < 0 || x >= m_nX || y >= m_nY || m_solution[y*m_nX+x] == -1 )
			return;
		m_solution[y*m_nX+x] = m_solution[y*m_nX+x] + 1;
	}

protected:
	int m_nX;
	int	m_nY;
	string m_strData;
	vector<int> m_solution;
};

void test1()
{
	solution sol;
	sol.setX(1);
	sol.setY(1);
	sol.setData("*");
	sol.solve();
	cout<<sol.getResult();
}

void test2()
{
	solution sol;
	sol.setX(2);
	sol.setY(1);
	sol.setData("*.");
	sol.solve();
	cout<<sol.getResult();
}

void test3()
{
	solution sol;
	sol.setX(2);
	sol.setY(2);
	sol.setData(
		"*."
		"..");
	sol.solve();
	cout<<sol.getResult();
}

void test4()
{
	solution sol;
	sol.setX(4);
	sol.setY(4);
	sol.setData(
		"*..."
		"...."
		".*.."
		"....");
	sol.solve();
	cout<<sol.getResult();
}

void main(int argc, char* argv[])
{
	test1();
	test2();
	test3();
	test4();
}

}}}