题目链接: 

题目大意：在不是X的地方放O，所有O在没有隔板情况下不能对视（横行和数列），问最多可以放多少个O。

解题思路：

题目规模比较小（4*4），可以DFS解决。

对于一个点，要么放，要么不放。

放的话条件必须是上下左右四个方向扫到边界且不首先碰到X。

可以只对放的点进行标记，而对于不放的点不进行标记，这样当dep>n*n的时候及时return就行了。

注意每次dfs只需要按顺序考虑一个点，而不要同时对整个棋盘所有非X点同时dfs，否则就爆了。

原因是，每次只关联一个点，其它点都是不关联的，如果dfs等于做了大量重复计算。

 

#include "cstdio"#include "string"#include "cstring"#include "iostream"using namespace std;int n,vis[5][5],ans;char map[5][5];struct status{    int x,y;    char type;    status(int x,int y,char type):x(x),y(y),type(type) {}    status() {}}P[20];bool judge(int X,int Y){    if(map[X][Y]=='X') return false;    for(int i=X-1; i>=1&&map[i][Y]!='X'; i--)  if(vis[i][Y]) return false;    for(int i=X+1; i<=n&&map[i][Y]!='X'; i++) if(vis[i][Y]) return false;    for(int i=Y-1; i>=1&&map[X][i]!='X'; i--) if(vis[X][i]) return false;    for(int i=Y+1; i<=n&&map[X][i]!='X'; i++)   if(vis[X][i]) return false;    return true;}void dfs(int p,int s){    if(p>n*n) {ans=max(ans,s);return;}    dfs(p+1,s);    vis[P[p].x][P[p].y]=true;    if(judge(P[p].x,P[p].y)) dfs(p+1,s+1);    vis[P[p].x][P[p].y]=false;}int main(){    //freopen("in.txt","r",stdin);    ios::sync_with_stdio(false);    string tt;    while(cin>>n&&n)    {        memset(vis,0,sizeof(vis));        int cnt=0;ans=0;        for(int i=1;i<=n;i++)        {            cin>>tt;            for(int j=0;j

 

11909497

2014-10-19 11:59:35

Accepted

0MS

292K

C++