QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#388924#4637. Cell Towerjames1BadCreeperWA 1053ms87784kbC++143.4kb2024-04-13 21:34:122024-04-13 21:34:12

Judging History

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

  • [2024-04-13 21:34:12]
  • 评测
  • 测评结果:WA
  • 用时:1053ms
  • 内存:87784kb
  • [2024-04-13 21:34:12]
  • 提交

answer

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

int a[15][15]; 
inline int id(int i, int j) { return (i << 3) + j; }
inline bool he(int x) { return x >= 0 && x < 8; }

map<ulong, ulong> mp; 
unordered_set<ulong> vis; 
bool dic3[1005], dic4[10005]; 
// 999
const int _3[6][2][2] = {
    {{0, 1}, {1, 0}}, 
    {{0, 1}, {1, 1}}, 
    {{1, 0}, {1, 1}}, 
    {{1, -1}, {1, 0}}, 
    {{0, 1}, {0, 2}}, 
    {{1, 0}, {2, 0}}
}; 
const int _4[19][3][2] = {
    {{1, 0}, {2, 0}, {3, 0}}, 
    {{0, 1}, {0, 2}, {0, 3}}, 
    {{1, 0}, {1, 1}, {1, 2}}, 
    {{1, -2}, {1, -1}, {1, 0}}, 
    {{1, -1}, {1, 0}, {1, 1}}, 
    {{0, 1}, {0, 2}, {1, 2}}, 
    {{0, 1}, {0, 2}, {1, 0}}, 
    {{0, 1}, {0, 2}, {1, 1}}, 
    {{0, 1}, {1, 0}, {2, 0}}, 
    {{1, 0}, {1, 1}, {2, 0}}, 
    {{0, 1}, {1, -1}, {1, 0}}, 
    {{1, 0}, {2, 0}, {2, 1}}, 
    {{0, 1}, {1, 1}, {2, 1}}, 
    {{1, -1}, {1, 0}, {2, 0}}, 
    {{1, 0}, {2, -1}, {2, 0}}, 
    {{1, 0}, {1, 1}, {2, 1}}, 
    {{1, -1}, {1, 0}, {2, -1}}, 
    {{0, 1}, {1, 0}, {1, 1}}, 
    {{0, 1}, {1, 1}, {1, 2}}
}; 

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0); 
    double st = clock(); 
    for (int i = 0; i < 8; ++i) 
        for (int j = 0; j < 8; ++j) 
            cin >> a[i][j]; 
    int m; cin >> m; 
    while (m--) {
        string x; cin >> x; 
        if (x.length() == 3) dic3[atoi(x.c_str())] = 1; 
        else dic4[atoi(x.c_str())] = 1; 
    }

    const ulong ED = -1; 

    mp[0] = 1; 
    queue<ulong> q[65]; q[0].push(0); 
    
    for (int et = 0; et < 62; ++et) while (!q[et].empty()) {
        ulong u = q[et].front(); q[et].pop(); 
        int i = -1; 
        for (i = 0; i < 64; ++i) if (!(u >> i & 1)) break; 
        int x = i >> 3, y = i & 7, abe = 0; 
        const ulong now = mp[u]; 
        for (int k = 0; k < 6; ++k) {
            int _x = x + _3[k][0][0], _y = y + _3[k][0][1]; 
            if (_x >= 8 || !he(_y) || (u >> id(_x, _y) & 1)) continue; 

            int __x = x + _3[k][1][0], __y = y + _3[k][1][1]; 
            if (__x < 8 && he(__y) && !(u >> id(__x, __y) & 1) && !dic3[a[x][y] * 100 + a[_x][_y] * 10 + a[__x][__y]]) {
                ulong v = (u | 1ull << id(x, y) | 1ull << id(_x, _y) | 1ull << id(__x, __y)); 
                mp[v] += now; 
                if (vis.find(v) == vis.end()) q[et + 3].push(v), vis.insert(v), abe = 1; 
            }
        }
        if (abe) {
            for (int k = 0; k < 19; ++k) {
                int _x = x + _4[k][0][0], _y = y + _4[k][0][1]; 
                if (_x >= 8 || !he(_y) || (u >> id(_x, _y) & 1)) continue; 
    
                int x_ = x + _4[k][1][0], y_ = y + _4[k][1][1]; 
                if (x_ >= 8 || !he(y_) || (u >> id(x_, y_) & 1)) continue; 
    
                int __x = x + _4[k][2][0], __y = y + _4[k][2][1]; 
                if (__x < 8 && he(__y) && !(u >> id(__x, __y) & 1) && !dic4[a[x][y] * 1000 + a[_x][_y] * 100 + a[x_][y_] * 10 + a[__x][__y]]) {
                    ulong v = (u | 1ull << id(x, y) | 1ull << id(_x, _y) | 1ull << id(x_, y_) | 1ull << id(__x, __y)); 
                    mp[v] += now; 
                    if (vis.find(v) == vis.end()) q[et + 4].push(v), vis.insert(v); 
                }
            }
        }
    }
    cout << mp[ED] << "\n"; 
    double ed = clock(); 
    cerr << (ed - st) * 1000 / CLOCKS_PER_SEC << "ms\n"; 
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1053ms
memory: 87784kb

input:

1 1 1 1 2 3 3 3
0 4 4 4 2 2 2 3
0 0 5 5 6 6 7 7
0 9 5 5 6 8 7 7
9 9 9 1 6 8 8 8
3 1 1 1 2 2 2 2
4 5 6 0 0 4 4 3
7 8 9 0 0 4 3 3
16
1111
2222
3333
444
0000
5555
6666
7777
8888
9999
111
333
3456
789
3478
569

output:

52990125641

result:

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