aoj 0612 - Sandcastle

問題

問題概要

省略

解法

今回の問題は毎回すべての城を調べていたら、TLEになってしまう。そこで、ポイントは、「n回目の波で崩れる城はn - 1回目の波で崩れた城の周囲8方向の城に限られる」ということである。そこで、まずは、城が存在する座標をq1に入れて、その中で崩れた城の周囲8方向の座標を q2に入れる。次に、q2に入っている城が崩れるかを調べて、崩れる城があった場合は、その座標の周囲8方向の座標を空になったq1にその座標を入れ、また同様なことを繰り返していけばいい。
q1からq2、q2からq1へ座標を入れる時、s(set)に一度入れることで、重複した座標を入れることを防いでいる。

ミス

下記は素直に毎回すべてのマスを全探索して、条件を満たす城を消しき、何回目で城が崩れなくなるかを調べたもの。TLE解。

#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

string board[1001];
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int h, w;
bool hantei(int y, int x){
    if(0 <= y && y < h && 0 <= x && x < w) return true;
    else return false;
}
int main(void){
    cin >> h >> w;
    rep(i, h) cin >> board[i];
    int ans = -1, nowy, nowx;
    bool flag = true;
    while(flag){
        flag = false; ans++;
        vector<pair<int, int> > memo;//一回の波で城が潰れる位置座標を記録しておく
        rep(y, h){
            rep(x, w){
                if(board[y][x] == '.') continue;
                int tmp = 0;
                rep(i, 8){
                    nowy = y + dy[i]; nowx = x + dx[i];
                    if(!hantei(nowy, nowx))continue;
                    if(board[nowy][nowx] == '.')tmp++;
                }
                if(tmp >= board[y][x] - '0'){
                    // board[y][x] = '.';ここで城を潰してはいけない
                    memo.push_back(make_pair(y, x));
                    flag = true;
                }
            }
        }
        //城を潰す
        rep(k, memo.size()){
            board[memo[k].first][memo[k].second] = '.';
        }
    }
    printf("%d\n", ans);
    return 0;
}

下記のコードはqueueを2つ使って書いたが、汚くて無駄なコードですね。嫌ですね。

コード

#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

string board[1001];
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int h, w;
bool hantei(int y, int x){
    if(0 <= y && y < h && 0 <= x && x < w) return true;
    else return false;
}

int main(void){
    cin >> h >> w;
    rep(i, h) cin >> board[i];
    queue<pair<int, int> > q1, q2;
    rep(i, h)rep(j, w){
        if(board[i][j] != '.') q1.push(make_pair(i, j));
    }

    int ans = -1, cnt = 0, nowy, nowx;
    bool flag = true;
    while(flag){
        flag = false; ans++;
        vector<pair<int, int> > memo;//一回の波で城が潰れる位置座標を記録しておく
        set<pair<int, int> > s;
        if(cnt % 2 == 0){
            while(!q1.empty()){//q1を使うとき
                pair<int, int> now = q1.front(); q1.pop();
                if(board[now.first][now.second] == '.') continue;
                int tmp = 0;
                rep(i, 8){
                    int nowy = now.first + dy[i], nowx = now.second + dx[i];
                    if(!hantei(nowy, nowx)) continue;
                    if(board[nowy][nowx] == '.')tmp++;
                }
                if(tmp >= board[now.first][now.second] - '0'){
                    memo.push_back(make_pair(now.first, now.second));
                    rep(k, 8){//城が崩れた周りの城は次の波で崩れる可能性があるので
                        int ny = now.first + dy[k], nx = now.second + dx[k];
                        if(!hantei(ny, nx)) continue;
                        if(board[ny][nx] != '.'){
                            s.insert(make_pair(ny, nx));
                        }
                    }
                    flag = true;
                }
            }
        }else{
            while(!q2.empty()){//q2を使うとき
                pair<int, int> now = q2.front(); q2.pop();
                if(board[now.first][now.second] == '.') continue;
                int tmp = 0;
                rep(i, 8){
                    int nowy = now.first + dy[i], nowx = now.second + dx[i];
                    if(!hantei(nowy, nowx)) continue;
                    if(board[nowy][nowx] == '.')tmp++;
                }
                if(tmp >= board[now.first][now.second] - '0'){
                    memo.push_back(make_pair(now.first, now.second));
                    rep(k, 8){//城が崩れた周りの城は次の波で崩れる可能性があるので
                        int ny = now.first + dy[k], nx = now.second + dx[k];
                        if(!hantei(ny, nx)) continue;
                        if(board[ny][nx] != '.'){
                            s.insert(make_pair(ny, nx));
                        }
                    }
                    flag = true;
                }
            }
        }
        //城を潰す
        rep(k, memo.size()){
            board[memo[k].first][memo[k].second] = '.';
        }
        if(cnt % 2 == 0){
            for(auto x : s) q2.push(make_pair(x.first, x.second));
        }else{
            for(auto x : s) q1.push(make_pair(x.first, x.second));
        }
        cnt++;
    }
    printf("%d\n", ans);
    return 0;
}