1 #include <iostream>
   2 #include <string>
   3 #include <fstream>
   4 #include <vector>
   5 #include <stdlib.h>
   6 #include <strstream>
   7 
   8 using namespace std;
   9 
  10 class solution{
  11 public:
  12         solution()
  13         {
  14                 m_nX = 0;
  15                 m_nY = 0;
  16                 m_strData.erase();
  17         }
  18 
  19         ~solution()
  20         {
  21         }
  22 
  23         void setX(int x)
  24         {
  25                 m_nX = x;
  26         }
  27 
  28         void setY( int y )
  29         {
  30                 m_nY = y;
  31         }
  32 
  33         void setData( string data )
  34         {
  35                 m_strData = data;
  36         }
  37 
  38         void solve()
  39         {
  40                 if ( m_strData.length() < m_nX * m_nY - 1 )
  41                         return;
  42                 
  43                 // clear solution
  44                 m_solution.clear();
  45                 for( int i = 0; i < m_nX; i++ )
  46                         for( int j = 0; j < m_nY; j++ )
  47                                 m_solution.push_back(0);
  48 
  49 
  50                 // calculate
  51                 int nIndex;
  52                 for( int y = 0; y < m_nY; y ++ )
  53                 {
  54                         for ( int x = 0; x < m_nX; x ++ )
  55                         {
  56                                 nIndex = y * m_nX + x;
  57                                 if( m_strData.at( nIndex ) == '*' )
  58                                 {
  59                                         addMine( x, y );        
  60                                 }
  61                         }
  62                 }
  63         }
  64 
  65         string getResult()
  66         {
  67                 int nIndex;
  68 
  69                 strstream result;
  70                 
  71                 for ( int y = 0; y < m_nY; y++ )
  72                 {
  73                         for ( int x = 0; x < m_nX; x ++ )
  74                         {
  75                                 nIndex = y * m_nX + x;
  76                                 if ( m_solution[nIndex] == -1 )
  77                                         result << '*';
  78                                 else
  79                                         result << m_solution[nIndex];
  80                         }
  81                         result<<'\n';
  82                 }
  83                 string strResult;
  84                 getline( result, strResult, ' ' );
  85                 return strResult + "\n";
  86         }
  87 
  88 protected:
  89         void addMine( int x, int y )
  90         {
  91                 m_solution[y*m_nX+x] = -1;
  92                 for( int i = x - 1; i <= x + 1; i ++ )
  93                         for ( int j = y - 1; j <= y + 1; j ++ )
  94                                 addHint( i, j );
  95         }
  96 
  97         void addHint( int x, int y )
  98         {
  99                 if ( x < 0 || y < 0 || x >= m_nX || y >= m_nY || m_solution[y*m_nX+x] == -1 )
 100                         return;
 101                 m_solution[y*m_nX+x] = m_solution[y*m_nX+x] + 1;
 102         }
 103 
 104 protected:
 105         int m_nX;
 106         int     m_nY;
 107         string m_strData;
 108         vector<int> m_solution;
 109 };
 110 
 111 void test1()
 112 {
 113         solution sol;
 114         sol.setX(1);
 115         sol.setY(1);
 116         sol.setData("*");
 117         sol.solve();
 118         cout<<sol.getResult();
 119 }
 120 
 121 void test2()
 122 {
 123         solution sol;
 124         sol.setX(2);
 125         sol.setY(1);
 126         sol.setData("*.");
 127         sol.solve();
 128         cout<<sol.getResult();
 129 }
 130 
 131 void test3()
 132 {
 133         solution sol;
 134         sol.setX(2);
 135         sol.setY(2);
 136         sol.setData(
 137                 "*."
 138                 "..");
 139         sol.solve();
 140         cout<<sol.getResult();
 141 }
 142 
 143 void test4()
 144 {
 145         solution sol;
 146         sol.setX(4);
 147         sol.setY(4);
 148         sol.setData(
 149                 "*..."
 150                 "...."
 151                 ".*.."
 152                 "....");
 153         sol.solve();
 154         cout<<sol.getResult();
 155 }
 156 
 157 void main(int argc, char* argv[])
 158 {
 159         test1();
 160         test2();
 161         test3();
 162         test4();
 163 }