简单DP

跳楼梯
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int Fib(int n){
    int prev1=1,prev2=2,prev3=4,prev4=8;
    int cur=0;
    if(n==1)cur=1;
    else if(n==2)cur=2;
    else if(n==3)cur=4;
    else if(n==4)cur=8;
    else{
        for(int i=5;i<=n;i++){
            cur=prev1+prev2+prev3+prev4;
            prev1=prev2;
            prev2=prev3;
            prev3=prev4;
            prev4=cur;
        }
    }
    return cur;
}
int main(){
    cin>>m;
    while(m--){
        scanf("%d",&n);
        printf("%d\n",Fib(n));
    }
    return 0;
}

DFS迷宫路径个数 能否走出 最短距离

#include<iostream>
using namespace std;
const int N = 10;
bool g[N][N];
int n,m,T,cnt;
 int ha,la,hb,lb;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void dfs(int ha,int la){
    if(ha==hb&&la==lb) {cnt++;return;}
    g[ha][la]=true;
    for(int i=0;i<4;i++){
        int x=ha+dx[i],y=la+dy[i];
        if(g[x][y])continue;
        if(x<1||x>n||y<1||y>m)continue;//注意
        //g[x][y]=true;
        dfs(x,y);
        //g[x][y]=false;
    }
    g[ha][la]=false;
}
int main(){
    cin>>n>>m>>T;
    cin>>ha>>la>>hb>>lb;
    while(T--){
        int x,y;
        cin>>x>>y;
        g[x][y]=true;
    }
    g[ha][la]=true;
    dfs(ha,la);
    cout<<cnt<<endl;
    return 0;
}
//1504
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=110;
char g[N][N];
int m,n;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool st[N][N];
bool dfs(int ha,int la){
    if(g[ha][la]=='#')return false;
    if(ha==n-1&&la==m-1)return true;
    st[ha][la]=true;
    for(int i=0;i<4;i++){
        int a=ha+dx[i],b=la+dy[i];
        if(a<0||a>=n||b<0||b>=m)continue;
        if(st[a][b])continue;
        if(dfs(a,b))return  true;
    }
    return false;
}
int main(){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)scanf("%s",g[i]);
        if(dfs(0,0))puts("Yes");
        else puts("No");
    return 0;
}
//15
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#define x first
#define y second
using namespace std;
int n,m;
const int N =110;
int g[N][N];
int d[N][N];
typedef pair<int,int>PII;
queue<PII>q;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int  bfs(){
    q.push({0,0});
    memset(d,-1,sizeof d);
    d[0][0]=0;
    while(q.size()){
        auto t=q.front();q.pop();
        for(int i=0;i<4;i++){
            int x=t.x+dx[i],y=t.y+dy[i];
            if(x<0||x>=n||y<0||y>=m||g[x][y]==1||d[x][y]!=-1)continue;//相反写勿忘d
            d[x][y]=d[t.x][t.y]+1;
            q.push({x,y});
        }
    }
    return d[n-1][m-1];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    scanf("%d",&g[i][j]);
    cout<<bfs();
    return 0;
}