洛谷P3848 [TJOI2007]跳棋

@Pelom  October 12, 2021

题意

数据范围:$1 \le n \le 100$

题解

数据范围较小,可直接$dfs$
越过连续$1$为

int nx=x+v[i][0],ny=y+v[i][1],cnt=1;
for(;nx>=1 && nx<=n && ny>=1 && ny<=n && a[nx][ny];nx+=v[i][0],ny+=v[i][1],cnt++);

因为必须越过至少$1$个$1$,所以$cnt$必须$>1$

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100+10;
int n,x,y;
bool a[N][N];
bool vis[N][N];
int ans;
int v[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y,int s){
    ans=max(ans,s);
    for(int i=0;i<4;i++){
        int nx=x+v[i][0],ny=y+v[i][1],cnt=1;
        for(;nx>=1 && nx<=n && ny>=1 && ny<=n && a[nx][ny];nx+=v[i][0],ny+=v[i][1],cnt++);
        if(nx>=1 && nx<=n && ny>=1 && ny<=n && !a[nx][ny] && !vis[nx][ny] && cnt!=1){
            vis[nx][ny]=1;
            dfs(nx,ny,s+cnt);
            vis[nx][ny]=0;
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&x,&y);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    vis[x][y]=1;
    dfs(x,y,0);
    printf("%d",ans);
    return 0;
}

添加新评论