bfs求调

HaloCode @ 2024-10-26 17:11:45

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 10;
int T;
char dt[MAXN][MAXN];
bool bj[MAXN][MAXN] = {0};

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

struct Node {
    int x, y, d;
};

bool inMap(int x, int y, int n, int m) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

int main() {
    cin >> T;

    while (T--) {
        int n, m, k;
        cin >> n;
        cin >> m;
        cin >> k;

        int sx, sy, sd;
        cin >> sx;
        cin >> sy;
        cin >> sd;

        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < m; j++) {
                dt[i][j + 1] = s[j];
            }
        }

        // bfs
        int head = 1, tail = 0, op = 0;
        Node dl[MAXN];
        dl[head].x = sx;
        dl[head].y = sy;
        dl[head].d = sd;
        bj[sx][sy] = 1;
        tail++;

        while (head <= tail && k > 0) {
            op = 0;
            Node cur = dl[head];
            int od = cur.d;
            int ox = cur.x + dx[od];
            int oy = cur.y + dy[od];

            if (inMap(ox, oy, n, m) && dt[ox][oy] == '.' &&!bj[ox][oy]) {
                tail++;
                dl[tail].x = ox;
                dl[tail].y = oy;
                dl[tail].d = od;
                bj[ox][oy] = 1;
            } else {
                op = 1;
                dl[tail].x = cur.x;
                dl[tail].y = cur.y;
                dl[tail].d = (od + 1) % 4;
            }

            if (op == 0) {
                head++;
            }
            k--;
        }

        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (bj[i][j]) {
                    cnt++;
                }
            }
        }

        cout << cnt << endl;
    }

    return 0;
}

by chenzhexuan1 @ 2024-10-26 17:45:00

终于找到一个一样用bfs的了

#include <iostream>
#include <queue>
#include <cstring>
#define N 1005
#define MOD 4
using namespace std;
struct Node{
    int x,y,d;
    Node(){}
    Node(int a,int b,int c):x(a),y(b),d(c){}
};
int t,n,m,k,sx,sy,sd;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
bool vis[N][N];
char mp[N][N];
int bfs(int sx,int sy,int sd){
    queue<Node> que;
    vis[sx][sy]=true;
    que.push(Node(sx,sy,sd));
    int step=0,ct=0;
    while(!que.empty()){
        Node u=que.front();
        que.pop();
        int d=u.d; 
        while(true){
            int x=u.x+dx[d],y=u.y+dy[d];
            if(0<x&&x<=n&&0<y&&y<=m&&mp[x][y]=='.'){
                que.push(Node(x,y,d));
                vis[x][y]=true;
                step++;
                break;
            }
            else{
                step++;
                d=(d+1)%MOD;
            }
            if(step==k)break;
        }
        if(step==k)break;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(vis[i][j])ct++;
        }
    }
    return ct;
}
int main(){
    cin>>t;
    while(t--){
        memset(vis,false,sizeof(vis));
        cin>>n>>m>>k>>sx>>sy>>sd;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)cin>>mp[i][j];
        }
        cout<<bfs(sx,sy,sd)<<endl;
    }
}

by shawn0618 @ 2024-10-26 17:59:54

好家伙，你的x是在列上走的，对吧

by HaloCode @ 2024-10-26 18:03:13

@shawn0618 ？

by shawn0618 @ 2024-10-26 18:04:59

我用的不是bfs啊

by HaloCode @ 2024-10-26 18:09:23

@shawn0618 x哪里从列上走的呀。没看出来呢

by shawn0618 @ 2024-10-26 18:10:02

还有你咋又re啊

by HaloCode @ 2024-10-26 18:10:53

@shawn0618 不知道啊

by shawn0618 @ 2024-10-26 18:13:37

测下来没问题。

你的x确实实在列上走的，因为边界条件是x<=n,而n代表的是列。

@HaloCode

by shawn0618 @ 2024-10-26 18:16:46

还有你第58行if (inMap(ox, oy, n, m) && dt[ox][oy] == '.' &&!bj[ox][oy])bj为啥要去重

by shawn0618 @ 2024-10-26 18:20:01

1
3 3 114514
1 1 1
...
.x.
.xx

测测这个。

正确答案显然可以走完整张地图，而你的答案是3