40分求助

scratch_szc @ 2024-10-26 22:50:30

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
#define int long long
#define INF LLONG_MAX
#define _INF LLONG_MIN
#define ios ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
using namespace std;
int fx[4]={0,1,0,-1};
int fy[4]={1,0,-1,0};
int n,m;
const int N=1e3+11;
char mp[N][N];
int res=1;
void print(int a,int b,int c,int d,int e){cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<'\n';}
void dfs(int x,int y,int d,int k){
    if(k==0)return ;
    int dx=x+fx[d];
    int dy=y+fy[d];
    if(mp[dx][dy]=='x'||dx<1||dx>n||dy<1||dy>m)dfs(x,y,(d+1)%4,k-1);
    else res++,dfs(dx,dy,d,k-1);
}
signed main(){
    ios
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>n>>m;
        int k;
        cin>>k;
        int xx,yy,dd;
        cin>>xx>>yy>>dd;
        for(int j=1;j<=n;j++)for(int z=1;z<=m;z++)cin>>mp[j][z];
        dfs(xx,yy,dd,k);
        cout<<res<<'\n';
        res=1;
    }
    return 0;
}

by Ahws_rwhy @ 2024-10-26 23:02:45

@scratch_szc 每个点可能有重复走过的

by scratch_szc @ 2024-10-26 23:03:14

@rwhy 标记？

by Ahws_rwhy @ 2024-10-26 23:04:00

@scratch_szc 1

by scratch_szc @ 2024-10-26 23:07:41

@rwhy 然后怎么改：

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
#define int long long
#define INF LLONG_MAX
#define _INF LLONG_MIN
#define ios ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
using namespace std;
int fx[4]={0,1,0,-1};
int fy[4]={1,0,-1,0};
int n,m;
const int N=1e3+11;
char mp[N][N];
int res=1;
void print(int a,int b,int c,int d,int e){cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<'\n';}
void dfs(int x,int y,int d,int k){
    if(k==0)return ;
    mp[x][y]='x';
    int dx=x+fx[d];
    int dy=y+fy[d];
    if(mp[dx][dy]=='x'||dx<1||dx>n||dy<1||dy>m)dfs(x,y,(d+1)%4,k-1);
    else res++,dfs(dx,dy,d,k-1);
}
signed main(){
    ios
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>n>>m;
        int k;
        cin>>k;
        int xx,yy,dd;
        cin>>xx>>yy>>dd;
        for(int j=1;j<=n;j++)for(int z=1;z<=m;z++)cin>>mp[j][z];
        dfs(xx,yy,dd,k);
        cout<<res<<'\n';
        res=1;
    }
    return 0;
}

40分

by Ahws_rwhy @ 2024-10-26 23:14:57

@scratch_szc 这样 50 了

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
#define int long long
#define INF LLONG_MAX
#define _INF LLONG_MIN
#define ios ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
using namespace std;
int fx[4] = {0, 1, 0, -1};
int fy[4] = {1, 0, -1, 0};
int n, m;
const int N = 1e3 + 11;
char mp[N][N];
bool vised[N][N];
int res = 1;
void print(int a, int b, int c, int d, int e) {
    cout << a << ' ' << b << ' ' << c << ' ' << d << ' ' << e << '\n';
}
void dfs(int x, int y, int d, int k) {
    if (k == 0)return ;
//  mp[x][y] = 'x';
    int dx = x + fx[d];
    int dy = y + fy[d];
    if (mp[dx][dy] == 'x' || dx < 1 || dx > n || dy < 1 || dy > m)dfs(x, y, (d + 1) % 4, k - 1);
    else if(mp[dx][dy] == '.' &&  vised[dx][dy] == 0) vised[dx][dy] = 1, res++, dfs(dx, dy, d, k - 1);
}
signed main() {
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        memset(vised , 0 , sizeof vised);
        cin >> n >> m;
        int k;
        cin >> k;
        int xx, yy, dd;
        cin >> xx >> yy >> dd;
        vised[xx][yy] = 1;
        for (int j = 1; j <= n; j++)for (int z = 1; z <= m; z++)cin >> mp[j][z];
        dfs(xx, yy, dd, k);
        cout << res << '\n';
        res = 1;
    }
    return 0;
}