赛时代码爆零为啥？

2023z @ 2024-10-26 16:04:49

#include<bits/stdc++.h>
#define int long long
using namespace std;
char a[1010][1010];
bool used[1010][1010];
int t,n,m,x1,g1,k1,d1,maxx=1;
void dfs(int x,int y,int d,int k,int s){
    if(x<1||x>n||y<1||y>m||a[x][y]=='x') return;
    if(s>maxx) maxx=s;
    if(k==k1){
        if(used[x][y]==0){
            if(s+1>maxx) maxx=s+1;
        }
        return;
    }
    if(used[x][y]==0){
        used[x][y]=true;
        if(d==0) dfs(x,y+1,d,k+1,s+1);
        if(d==1) dfs(x+1,y,d,k+1,s+1);
        if(d==2) dfs(x,y-1,d,k+1,s+1);
        if(d==3) dfs(x-1,y,d,k+1,s+1);
    }
    else if(used[x][y]==1){
        if(d==0) dfs(x,y+1,d,k+1,s);
        if(d==1) dfs(x+1,y,d,k+1,s);
        if(d==2) dfs(x,y-1,d,k+1,s);
        if(d==3) dfs(x-1,y,d,k+1,s);
    }
    dfs(x,y,(d+1)%4,k+1,s);
    used[x][y]=false;
}
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>m>>k1;
        cin>>x1>>g1>>d1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
        }
        dfs(x1,g1,d1,0,1);
        cout<<maxx<<endl;
        maxx=1;
    }
    return 0;
}

by Jiangyixuan0330 @ 2024-10-26 16:09:21

这只是一道模拟,可以不用DFS

by epmmd @ 2024-10-26 16:10:15

你想太复杂了

by Loyal_Soldier @ 2024-10-26 16:11:19

@2023z 我用dfsAC的代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,ans;
int dx[10]={0,1,0,-1};
int dy[10]={1,0,-1,0};
int cnt[1100][1100];
char c[1100][1100];
void dfs(int x,int y,int d,int s){
    if(s>k)
        return;
    if(cnt[x][y]==0)
        ans++;
    cnt[x][y]++;
    int nx=x+dx[d];
    int ny=y+dy[d];
    if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&c[nx][ny]!='x')
        dfs(nx,ny,d,s+1);
    else
        dfs(x,y,(d+1)%4,s+1);
}
signed main(){
    int T;
    cin>>T;
    while(T--){
        ans=0;
        memset(cnt,0,sizeof(cnt));
        int a,b,v;
        cin>>n>>m>>k;
        cin>>a>>b>>v;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>c[i][j];
        dfs(a,b,v,0);
        cout<<ans<<endl;
    }
    return 0;
}

by Loyal_Soldier @ 2024-10-26 16:12:40

顺便恭喜你T2爆零

by 2023z @ 2024-10-26 16:12:43

谢谢dallao

by YR123 @ 2024-10-26 16:27:38

@2023z我的模拟代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include<unordered_map>
#include<queue>
#include<stack>
using namespace std;
int t,n,m,k,x,y,d;
char a[1005][1005];
bool vis[1005][1005];
bool check(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]=='.';
}
int main(){
    cin>>t;
    while(t--){
        int ans=0;
        cin>>n>>m>>k;
        cin>>x>>y>>d;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
            }
        }
        vis[x][y]=1;
        while(k--){
            int tx,ty;
            if(d==0){
                tx=x;
                ty=y+1;
                if(check(tx,ty)){
                    x=tx,y=ty;
                }
                else d=(d+1)%4;
            }
            else if(d==1){
                tx=x+1;
                ty=y;
                if(check(tx,ty)){
                    x=tx,y=ty;
                }
                else d=(d+1)%4;
            }
            else if(d==2){
                tx=x;
                ty=y-1;
                if(check(tx,ty)){
                    x=tx,y=ty;
                }
                else d=(d+1)%4;
            }
            else if(d==3){
                tx=x-1;
                ty=y;
                if(check(tx,ty)){
                    x=tx,y=ty;
                }
                else d=(d+1)%4;
            }
            vis[x][y]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(vis[i][j]==1){
                    ans++;
                }
            }
        }
        cout<<ans<<'\n';
        memset(vis,0,sizeof(vis));
    }
    return 0;
}

by wizza23 @ 2024-10-26 16:39:57

@YR123 我跟你写的好像