清北NOIP训练营独家内部训练试题！

清北NOIP2017训练营内部试题，2018年更多训练营等你参加！

解析在代码后面

#include

#include

using namespace std;

char s[11];

int mp[11][11];

bool mp2[11][11],vis[11][11];

int cnt,mx,tot;

struct node

{

    int x,y;

}ans[101];

int dx[4]={-1,-1,1,1};

int dy[4]={-1,1,1,-1};

void init()

{

    for(int i=1;i<>

    {

        scanf('%s',s+1);

        for(int j=1;j<=10;j++) mp[i][j]="">

    }

    for(int i=1;i<>

    {

        scanf('%s',s+1);

        for(int j=1;j<=10;j++) mp2[i][j]="">

    }

}

bool inmap(int x,int y)

{

    return (!(x<=0) &&="" !(x="">10) && !(y<=0) &&="" !(y="">10));

}

bool empty(int x,int y)

{

    return !mp[x][y];

}

bool jump(int x,int y)

{

    if(!inmap(x,y)) return false;

    return mp[x][y]==2;

}

bool have(int x,int y)

{

    return vis[x][y];

}

void update(int i,int j)

{

    if(cnt>mx)

    {

        mx=cnt; tot=1;

        ans[1].x=i; ans[1].y=j;

    }

    else if(cnt==mx) 

    {

        ans[++tot].x=i; ans[tot].y=j;

    }

}

void dfs(int x,int y,int sx,int sy)

{

    vis[x][y]=true;

    for(int i=0;i<>

        if(jump(x+dx[i],y+dy[i]) && inmap(x+dx[i]+dx[i],y+dy[i]+dy[i]) && empty(x+dx[i]+dx[i],y+dy[i]+dy[i]))

        {

            if(have(x+dx[i],y+dy[i]) || have(x+dx[i]+dx[i],y+dy[i]+dy[i]) ) continue;

            cnt++; update(sx,sy);

            dfs(x+dx[i]+dx[i],y+dy[i]+dy[i],sx,sy);

            cnt--;

        }

    vis[x][y]=false;

}

void dfs2(int x,int y,int sx,int sy)

{

    vis[x][y]=true;

    for(int d=0;d<>

    {

        int nx=x,ny=y;

        for(int i=1;i<>

        {

            nx+=dx[d]; ny+=dy[d];

            if(!inmap(nx,ny)) break;

            if(mp[nx][ny]==1) break;

            if(!jump(nx,ny)) continue;

            if(have(nx,ny)) continue;

            vis[nx][ny]=true;

            int nnx=nx,nny=ny;

            for(int j=1;j<>

            {

                nnx+=dx[d]; nny+=dy[d];

                if(!inmap(nnx,nny)) break;

                if(!empty(nnx,nny)) break;

                if(have(nnx,nny)) continue;

                cnt++;  update(sx,sy);

                dfs2(nnx,nny,sx,sy);

                cnt--;

            }

            vis[nx][ny]=false;

        }

    }

    vis[x][y]=false;

}

void solve()

{

    for(int i=1;i<>

        for(int j=1;j<>

            if(mp[i][j]==1) 

            {

                if(!mp2[i][j]) dfs(i,j,i,j);

                else dfs2(i,j,i,j);

            }

    if(!mx)

    {

        cnt=1;

        for(int i=1;i<>

            for(int j=1;j<>

                if(mp[i][j]==1)

                {

                    if(!mp2[i][j])

                    {        

                        for(int k=0;k<>

                            if(inmap(i+dx[k],j+dy[k]) && empty(i+dx[k],j+dy[k])) update(i,j);

                    }

                    else

                    {

                        for(int k=0;k<>

                        {

                            int nx=i,ny=j;

                            for(int l=1;l<>

                            {

                                nx+=dx[k];ny+=dy[k];

                                if(!inmap(nx,ny)) break;

                                if(!empty(nx,ny)) break;

                                update(i,j);

                            }

                        }

                    }

                }

                

    }

    printf('%d\n',tot);

    for(int i=1;i<=tot;i++)>

}

int main()

{

    freopen('chess.in','r',stdin);

    freopen('chess.out','w',stdout);

    init();

    solve();

}

实际上加冕没有用

这种题最好先打出裸的dfs

◆ ◆ 

好

消

息

由清北学堂信息学金牌教研团队策划的