题解 P3848 【[TJOI2007]跳棋】

犇犇犇犇 · 2018-12-14 21:48:47 · 题解

先看数据范围，这道题n（1≤n≤100），所以一个dfs就可以过了。

但是还是把我卡了好久。

这道题稍微难一点的地方就是dfs的时候从0开始不碰到下一个0或者边界永不停止。
所以自然可以想到用while语句。
我们用dx,dy来表示向四个方向移动。用变量s来统计从这个0到下一个0的步数。

    int tx=x,ty=y,s=0;
    while(tx+dx[i]>0 && tx+dx[i]<=n && ty+dy[i]>0 && ty+dy[i]<=n) //碰到边界
    {
        tx+=dx[i];
        ty+=dy[i]; 
        s++;  //走到下一个点
        if(m[tx][ty]==0) break; //走到目标！
    }

下面就可以很愉快的打dfs模板了。

要注意的是，当我们的步数s=1时情况为两个0相连，同样不满足要求

上代码

#include <bits/stdc++.h>
using namespace std;     
int n,i,j,k,ans;
int m[105][105],f[105][105]; //m表示棋盘，f统计这个点是否走过
int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1}; //dx,dy表示四向移动
void dfs(int x,int y,int step) 
{
    int i;
    ans=max(ans,step); //更新ans
    for(i=0;i<4;i++) 
    {
        int tx=x,ty=y,s=0;
        while(tx+dx[i]>0 && tx+dx[i]<=n && ty+dy[i]>0 && ty+dy[i]<=n) 
        {
            tx+=dx[i];
            ty+=dy[i];
            s++;
            if(m[tx][ty]==0) break;
        } //如上述
        if(tx>0 && tx<=n && ty>0 && ty<=n && f[tx][ty]==0 && m[tx][ty]==0 && s!=1) //碰壁，走过，当前格子为0，两个0相连都不能走
        {
            f[tx][ty]=1;
            dfs(tx,ty,step+s); //走到下一个点
            f[tx][ty]=0; //回溯
        }
    }
}
int main() 
{
    int x,y,i,j;
    cin>>n>>x>>y;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            cin>>m[i][j];
    f[x][y]=1; //出发点被走过了，所以要单独写
    dfs(x,y,0); 
    cout<<ans<<endl;
    return 0;   
}