p1434[shoi2002]滑雪(21.10.21)(代码片段)

原题链接
题意：分析：因为题目没有要求起点，也就是二维数组任意一个位置都可以作为起点向四周发散，所以想到用搜索。
可以用深度优先搜索算法解决，需要另设一个二维数组存储当前位置是否走过。
详细解释见代码。

#include<iostream>
int a[105][105],d[105][105];
int n,m,ans=0;
using namespace std;
bool check(int a,int b)//判断该位置是否越界

    if(a<=0||b<=0||a>n||b>n)
        return 0;
    else return 1;

int dir[4][2]= -1,0,0,-1,1,0,0,1;//控制四个方向的移动
int dfs(int x,int y)

    if(d[x][y])//如果走过了，直接返回该位置可构建的长度即可。
        return d[x][y];
    int num=0;//这里是把x，y位置当做起点记录
    for(int i=0; i<4; i++)//4个方向循环
    
        int newx=x+dir[i][0];
        int newy=y+dir[i][1];
        if(check(newx,newy)&&a[x][y]<a[newx][newy])
            num=max(dfs(newx,newy),num);//找到四个方向中最长的路径
    
    num++;//当前位置，长度在之前的基础上加一
    return d[x][y]=num;//返回现在的长度

int main( )

    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>a[i][j];
    for(int i=1; i<=n; i++)
    
        for(int j=1; j<=m; j++)
        
                ans=max(ans,dfs(i,j));//从所有起点里找到最大值
        
    
    cout<<ans<<endl;

这个题有点像Red and Black
DFS做法：

#include<bits/stdc++.h>
using namespace std;
char room[23][23];
int dir[4][2]= -1,0,0,-1,1,0,0,1;
int Wx, Hy, num;
#define CHECK(x, y) (x<Wx && x>=0 && y >=0 && y<Hy)
struct node

    int x,y;
;
void DFS(int dx, int dy)

    room[dx][dy] = '#';
    num++;
    for(int i = 0; i < 4; i++)
    
        int newx = dx + dir[i][0];
        int newy = dy + dir[i][1];
        if(CHECK(newx, newy) && room[newx][newy] == '.')
        
            DFS(newx, newy);
        
    

int main()

    int x, y, dx, dy;
    while(cin>>Wx>>Hy)
    
        if(Wx==0&&Hy==0)
            break;
        for (y = 0; y < Hy; y++)
        
            for (x = 0; x < Wx; x++)
            
                cin >> room[x][y];
                if(room[x][y] == '@')
                
                    dx = x;
                    dy = y;
                
            
        
        num = 0;
        DFS(dx, dy);
        cout << num << endl;
    

    return 0;

BFS做法：

#include<bits/stdc++.h>
using namespace std;
char room[23][23];
int dir[4][2]= 
    -1,0,//向左
    0,-1,//向上
    1,0,//向右
    0,1//向下
;
int Wx,Hy,num;
#define CHECK(x,y)(x<Wx&&x>=0&&y>=0&&y<Hy
struct node

    int x,y;
;
void BFS(int dx,int dy)

    num=1;
    queue<node>q;
    node start,next;
    start.x=dx;
    start.y=dy;
    q.push(start);
    while(!q.empty())
    
        start=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        
            next.x=start.x+dir[i][0];
            next.y=start.y+dir[i][1];
            if(CHECK(next.x,next.y)&&room[next.x][next.y]=='.')
            
                room[next.x][next.y]='#';
                num++;
                q.push(next);
            
        
    

int main()

    int x,y,dx,dy;
    while(cin>>Wx>>Hy)
    
        if(Wx==0&&Hy==0)
            break;
        for(y=0;y<Hy;y++)
        
            for(x=0;x<Wx;x++)
            
                cin>>room[x][y];
                if(room[x][y]=='@')
                
                    dx=x;
                    dy=y;
                
            
        
        num=0;
        BFS(dx,dy);
        cout<<num<<endl;
    
    return 0;