学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1045

刚开始也不知道怎么做，用了下搜索，但本人做不下去了。

后来想到既然是贪心题目，那就贪心把，能放就放，就添加了一个 isok。

下面这个代码是第二次在[kuangbin带你飞]专题提交的代码：

思路是：枚举起点，然后按从左到右，从上到下的顺序放置，能放就放，然后dfs。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;


char Map[10][10];
int vis[10][10];
int N;

int isok(int x,int y){
    for(int i=x+1;i<N;i++)
        if(Map[i][y]=='X') break;
        else if(vis[i][y]) return 0;
    for(int i=x-1;i>=0;i--)
        if(Map[i][y]=='X') break;
        else if(vis[i][y]) return 0;
    for(int j=y+1;j<N;j++)
        if(Map[x][j]=='X') break;
        else if(vis[x][j]) return 0;
    for(int j=y-1;j>=0;j--)
        if(Map[x][j]=='X') break;
        else if(vis[x][j]) return 0;
    return 1;
}
int ans;

void dfs(int x,int y,int count){
    ans=max(ans,count);
    for(int j=y+1;j<N;j++)
        if(Map[x][j]!='X' && !vis[x][j] && isok(x,j)){
            vis[x][j]=1;
            dfs(x,j,count+1);
            vis[x][j]=0;
        }
    for(int i=x+1;i<N;i++)
        for(int j=0;j<N;j++)
            if(Map[i][j]!='X' && !vis[i][j] &&isok(i,j)){
                vis[i][j]=1;
                dfs(i,j,count+1);
                vis[i][j]=0;
            }
}
int main(){
    while(cin>>N && N)
    {
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                cin>>Map[i][j];
        ans=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++)
                if(Map[i][j]!='X'){
                    memset(vis,0,sizeof(vis));
                    vis[i][j]=1;
                    dfs(i,j,1);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}