zju1002-Fire Net

搜尋，深度優先周遊；

判斷每個單元格能否放置碉堡，如果可以，制‘O’，計數器加一，該方案遞歸完畢，單元格恢複；本單元格不放碉堡，進行方案遞歸。

#include<iostream>
#include<cstdio> 

using namespace std;

char cMap[4][4];
int ibest, n; 

bool can(int row, int col)
{
     int i;
     for(i = row - 1; i >= 0; i--)
     {
           if(cMap[i][col] == 'O') return false;
           if(cMap[i][col] == 'X') break;
     }
     for(i = col - 1; i >= 0; i--)
     {
           if(cMap[row][i] == 'O') return false;
           if(cMap[row][i] == 'X') break;
     }
     return true;
}

void solve(int k, int cur)
{
     int x, y;
     if(k == n * n)
     {
          if(cur > ibest)
          {
                 ibest = cur;
                 return;
          }
     }
     else
     {
         x = k / n;
         y = k % n;
         if(cMap[x][y] == '.' && can(x, y))
         {
                       cMap[x][y] = 'O';
                       solve(k + 1, cur + 1); 
                       cMap[x][y] = '.';
         }
         solve(k + 1, cur); 
     }
}

int main()
{
    int i, j;
    while(cin >> n && n)
    {
              for(i = 0; i < n; i++)
                  for(j = 0; j < n; j++)
                      cin >> cMap[i][j];
              ibest = 0;
              solve(0, 0);
              cout << ibest << endl;
    }
    return 0;
}