7月25日课堂练习

thomas1234567 · 2025-07-26 10:13:41 · 个人记录

|第一题：

|编号： P1958|名称：上学路线|难度： 普及−|提供者： 洛谷|

|第二题：

|编号： P1683|名称： 入门|难度： 普及−|提供者： yeszy|

|第三题：

|编号： U587530|名称：迷宫的第一条 出路|难度： 暂无评定|提供者： 齐芒|

第一题

可用： 模拟 ，搜索，递推

代码：

#include<bits/stdc++.h>
using namespace std;
int vis[100][100];
int ax[]={0,1};
int by[]={1,0};
int a,b;
int ans=0;
bool cheak(int x,int y){
    return (x>=1 && x<=a && y>=1 && y<=b && vis[x][y]==0);
}
void dfs(int x,int y){
    if(x==a && y==b){
        ans++;
        return ;
    }
    for(int i=0;i<2;i++){
        int xx=x+ax[i];
        int yy=y+by[i];
        if(cheak(xx,yy)){
            vis[xx][yy]=1;
            dfs(xx,yy);
            vis[xx][yy]=0;
        }
    }
}
int main()
{
    cin>>a>>b;
    int k;
    cin>>k;
    while(k--){
        int q,w;
        cin>>q>>w;
        vis[q][w]=1;
    }
    dfs(1,1);
    cout<<ans;
    return 0;
}

第二题

可用： 搜索

代码：

#include<bits/stdc++.h>
using namespace std;
int vis[25][25];
char a[25][25];
int dx[]={0,1,-1,0};
int dy[]={1,0,0,-1};
int n,m;
int sx,sy;
int ans=0;
bool cheak(int x,int y){
    return (x>=1 && x<=n && y>=1 && y<=m && vis[x][y]==0 && a[x][y]!='#');
}
void dfs(int x,int y){
    ans++;
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(cheak(xx,yy)){
            vis[xx][yy]=1;
            dfs(xx,yy);
        }
    }
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='@'){
                sx=i;
                sy=j;
            }
        }
    }
    dfs(sx,sy);
    cout<<ans-1<<endl;
    return 0;
}

第三题

可用： 搜索

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=25;
char ss[N][N];
char a[N][N];
bool vis[N][N];
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
int n;
struct node{
    int x,y;
};
vector<node> ans;
bool cheak(int x,int y){
    return (x>=1 && x<=n && y>=1 && y<=n && vis[x][y]==0 && a[x][y]!='1');
}
void print(){
    cout<<"(1,1)";
    for(int i=0;i<ans.size();i++){
        cout<<"->"<<"("<<ans[i].x<<","<<ans[i].y<<")";
    }
    return ;
} 
void dfs(int x,int y){
    if(x==n && y==n){
        print();
        return ;
    }
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(cheak(xx,yy)){
            vis[xx][yy]=1;
            ans.push_back({xx,yy});
            dfs(xx,yy);
            ans.pop_back();
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    vis[1][1] = 1;
    dfs(1,1);
    return 0;
}