發表新討論
#38208: 卡常解法


aslanchen0730@gmail.com (陌語)

學校 : 不指定學校
編號 : 164685
來源 : [114.42.11.98]
最後登入時間 ：
2023-05-17 23:57:53
c520. 5. 寶島老闆 -- 2017高雄市資訊學科能力複賽 | From: [140.128.251.133] | 發表日期 : 2023-11-03 19:22

這題我在做的時候被卡常數卡到爛掉

直到加了下面這幾個優化 + 把 BFS 的 queue 換成 vector 才過的

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma loop-opt(on)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,tune=native")

這邊附上我的 Code

/* Question : ZeroJudge c520. 5. Boss Baodao */

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma loop-opt(on)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,tune=native")
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define priq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 6e3 + 50;
const int Mod = 1e9 + 7;
int h, w, n, res, x, y;
char grid[MAXN][MAXN];
bool used[MAXN][MAXN];
vector<pii> q, nxtq;

signed main(){
    opt;
    cin >> h >> w;
    for( int i = 0 ; i < h ; i++ ) cin >> grid[i];

    cin >> n;
    for( int i = 0 ; i < n ; i++ ){
        cin >> x >> y;
        x--; y--;
        if( !used[x][y] ){
            used[x][y] = true;
            q.pb({x, y});
        }

        while ( !q.empty() ) {
            auto [x, y] = q.back();
            q.pop_back();
            res++;

            for( int d = 0 ; d < 4 ; d++ ){
                int nx = x + dir[d].f;
                int ny = y + dir[d].s;

                if( nx < 0 || nx >= h || ny < 0 || ny >= w ) continue;
                if( grid[nx][ny] == '#' ) continue;
                if( used[nx][ny] == true ) continue;

                used[nx][ny] = true;
                nxtq.pb({nx, ny});
            }
        }

        swap(q, nxtq);
        cout << res << '\n';
    }
}
 
ZeroJudge Forum