码风良好,逻辑基本正确,求调
查看原帖
码风良好,逻辑基本正确,求调
511229
Optics楼主2024/7/31 11:04
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1e3 + 10;
const int M = 1e4 + 10;
int T;
int n,r,c;
int sx,sy,ex,ey;
int lft,rgt,mid,ans,cnt;
int xa[M],ya[M],dis[N][N];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int vis[N][N];

struct node{
    int x,y,step;
};

bool check(int t){
    if(dis[ex][ey] < t)
        return false;
    memset(vis,0,sizeof(vis));
    int ret = 0;
    queue<node> q;
    q.push({sx,sy,0});
    vis[sx][sy] = -1;
    while(!q.empty()){
        node f = q.front();
        q.pop();
        if(f.x == ex && f.y == ey){
            if(ans < t){
                ans = t;
                cnt = vis[ex][ey];   
            }
            if(ans == t){
                cnt = min(cnt,vis[ex][ey]);
            }
            return true;
        }
        for(int i = 0; i < 4; i++){
            int nx = dx[i] + f.x;
            int ny = dy[i] + f.y;
            if(nx >= 1 && nx <= r && ny >= 1 && ny <= c && vis[nx][ny]  == 0 && dis[nx][ny] >= t){
                vis[nx][ny] = f.step + 1;
                // if()
                    q.push({nx,ny,f.step+1});
            }
        }
        // for(int i = 1; i <= r; i++){
        //     for(int j = 1; j <= c; j++)
        //         cout << vis[i][j] << " ";
        //     cout << endl;
        // }
        // cout << endl;
    }
    return false;
}

void init(){
    ans = 0;
    cnt = 1e9;
    memset(dis,0x3f,sizeof(dis));
    queue<node> q;
    for(int i = 1; i <= n; i++){
        q.push({xa[i],ya[i],0});
        dis[xa[i]][ya[i]] = 0;
    }
    while(!q.empty()){
        node f = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = f.x + dx[i];
            int ny = f.y + dy[i];
            if(nx >= 1 && nx <= r && ny >= 1 && ny <= c && dis[nx][ny] > f.step + 1){
                q.push({nx,ny,f.step+1});
                dis[nx][ny] = f.step + 1;
            }
        }
    }
}

int main(){
    cin >> T;
    while(T--){
        cin >> n >> r >> c;
        cin >> sx >> sy >> ex >> ey;
        sx++,sy++,ex++,ey++;
        for(int i = 1; i <= n; i++){
            cin >> xa[i] >> ya[i];    
            xa[i]++,ya[i]++;
        }
        init();
        // for(int i = 1; i <= r; i++){
        //     for(int j = 1; j <= c; j++)
        //         cout << dis[i][j] << " ";
        //     cout << endl;
        // }
        lft = 0;
        rgt = r * c;
        while(lft <= rgt){
            mid = lft + rgt >> 1;
            if(check(mid))
                lft = mid + 1;
            else
                rgt = mid - 1;
        }
        cout << ans << " " << cnt << endl;
    }

    return 0;
}

2024/7/31 11:04
加载中...