QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69171#3128. Rush Hour Puzzlezijun0502WA 3ms3384kbC++144.5kb2022-12-24 18:03:122022-12-24 18:03:13

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-24 18:03:13]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3384kb
  • [2022-12-24 18:03:12]
  • 提交

answer

#include<iostream>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<queue>
#include<deque>
#include<list>
#include<math.h>
#include<cmath>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>

using namespace std;
typedef long long ll;
#define vt vector
#define ull unsigned ll
#define ui unsigned int
#define vt vector
#define vc vt<char>
#define vb vt<bool>
#define vi vt<int>
#define vll vt<ll>
#define vvi vt<vi>
#define vvc vt<vc>
#define vvll vt<vll>
#define vpii vt<pair<int,int>>
#define vpll vt<pll>
#define vpci vt<pair<char,int>>
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pci pair<char, int>
#define pic pair<char, char>
#define pcll pair<char, ll>
#define psll pair<string, ll>
#define psi pair<string, int>
#define umii unordered_map<int,int>
#define umll unordered_map<ll, ll>
#define umci unordered_map<char, i>
#define umcl unordered_map<char, ll>
#define For(i, n) for(int i = 0 ; i < n ; i++)
#define FOR(i, n , m) for(int i = n ; i < m ; i++)
#define reset(i) memset(i, 0, sizeof(i))
#define pb push_back
#define f first
#define s second
template<class T>
void read(vector<T>& v) {
    for (auto& i : v) {
        cin >> i;
    }
}
template<class T>
void read(vector<pair<T, T>>& v) {
    for (auto& i : v) {
        cin >> i.f >> i.s;
    }
}
template<class T>
void sort(vector<T>& v) {
    sort(v.begin(), v.end());
}
template<class T>
void sort(vector<T>& v, int flag) {
    sort(v.begin(), v.end(), greater<T>());
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    if (vec.size() == 1) {
        os << vec[0];
    }
    else {
        typename vector<T>::const_iterator i;
        for (i = vec.begin(); i != vec.end() - 1; i++) {
            os << *i << " ";
        }
        os << *i;
    }
    os << '\n';
    return os;
}
void solve() {

}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    vvi b(6, vi(6));
    For(i, 6) {
        For(j, 6) {
            cin >> b[i][j];
        }
    }
    int dis = 0;
    auto check = [&](vvi& v) {
        for (int i = 5; i >= 0; i--) {
            if (v[2][i] != '0') {
                if (v[2][i] != '1') return 0;
                else{
                dis = 2 + 5 - i;
                return 1;
                }
            }
        }
        return 1;
    };
    auto valid = [](int i, int j) {
        return i >= 0 && i < 6 && j >= 0 && j < 6;
    };
    const int dir[2][2] = { {1,0},{0,1} };
    queue<pair<int, vvi>> q;
    set<vvi> se;
    q.push({ 0, b });
#define EMP(i, j) b[i][j] == '0'
    while (!q.empty()) {
        auto now = q.front();
        vvi& b = now.s;
        q.pop();
        if (now.f >= 10) break;
        if (se.count(b)) continue;
        se.insert(b);
        // For(i, 6) {
        //     For(j, 6) {
        //         cout << b[i][j];
        //     }cout << '\n';
        // }cout << '\n';
        if (check(now.s)) {
            cout << now.f + dis << '\n';
            return 0;
        }
        For(i, 6) {
            For(j, 6) {
                if (b[i][j] != '0' && b[i][j] != '1') {
                    for (auto d : dir) {
                        int ii = i + d[0], jj = j + d[1];
                        if (valid(i - d[0], j - d[1]) && b[i][j] == b[i - d[0]][j - d[1]]) continue;
                        if (valid(ii, jj) && b[i][j] != b[ii][jj] || !valid(ii, jj)) continue;
                        while (valid(ii, jj) && b[i][j] == b[ii][jj])
                        {
                            ii += d[0], jj += d[1];
                        }
                        pii h = { i - d[0], j - d[1] }, t = { ii, jj };
                        if (valid(h.f, h.s) && EMP(h.f, h.s)) {
                            b[h.f][h.s] = b[i][j];
                            b[ii - d[0]][jj - d[1]] = '0';
                            q.push({ now.f+1, b });
                            b[ii - d[0]][jj - d[1]] = b[h.f][h.s];
                            b[h.f][h.s] = '0';
                        }
                        if (valid(ii, jj) && EMP(ii, jj)) {
                            b[ii][jj] = b[i][j];
                            b[i][j] = '0';
                            q.push({ now.f+1, b });
                            b[i][j] = b[ii][jj];
                            b[ii][jj] = '0';
                        }
                    }
                }
            }
        }
    }
    cout << -1 << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3376kb

input:

2 2 0 0 0 7
3 0 0 5 0 7
3 1 1 5 0 7
3 0 0 5 0 0
4 0 0 0 8 8
4 0 6 6 6 0

output:

-1

result:

ok single line: '-1'

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3384kb

input:

0 2 0 6 6 0
0 2 0 0 7 0
0 3 1 1 7 0
0 3 4 4 8 0
0 5 5 5 8 0
0 0 0 0 0 0

output:

-1

result:

wrong answer 1st lines differ - expected: '6', found: '-1'