QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#69168 | #3128. Rush Hour Puzzle | zijun0502 | WA | 6ms | 4968kb | C++14 | 4.5kb | 2022-12-24 18:00:47 | 2022-12-24 18:00:49 |
Judging History
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);
vvc b(6, vc(6));
For(i, 6) {
For(j, 6) {
cin >> b[i][j];
}
}
int dis = 0;
auto check = [&](vvc& 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, vvc>> q;
set<vvc> se;
q.push({ 0, b });
#define EMP(i, j) b[i][j] == '0'
while (!q.empty()) {
auto now = q.front();
vvc& 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: 4ms
memory: 4032kb
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: 0
Accepted
time: 2ms
memory: 3344kb
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:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3436kb
input:
0 2 6 6 6 0 0 2 0 0 7 0 0 3 1 1 7 0 0 3 4 4 8 0 0 0 5 5 8 0 0 0 0 0 0 0
output:
8
result:
ok single line: '8'
Test #4:
score: 0
Accepted
time: 6ms
memory: 4968kb
input:
2 3 4 4 4 5 2 3 6 7 7 5 0 3 6 1 1 5 0 0 0 0 0 0 0 0 0 0 8 8 0 0 0 9 9 9
output:
8
result:
ok single line: '8'
Test #5:
score: 0
Accepted
time: 3ms
memory: 3568kb
input:
0 2 6 6 6 0 0 2 4 0 7 0 1 1 4 0 7 0 0 3 4 5 0 8 0 3 0 5 0 8 0 3 0 0 0 8
output:
10
result:
ok single line: '10'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3384kb
input:
0 2 6 6 6 7 0 2 4 0 0 7 1 1 4 0 0 7 0 3 4 5 0 8 0 3 0 5 0 8 0 3 0 0 0 8
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3416kb
input:
0 2 3 4 4 4 0 2 3 5 5 5 1 1 0 0 0 0 0 6 7 7 0 10 0 6 8 8 8 10 0 6 0 9 9 10
output:
6
result:
ok single line: '6'
Test #8:
score: -100
Wrong Answer
time: 1ms
memory: 3468kb
input:
0 2 2 2 4 4 5 5 3 3 0 0 1 1 0 6 0 0 0 0 0 6 0 10 0 0 0 7 9 10 0 8 8 7 9 10
output:
7
result:
wrong answer 1st lines differ - expected: '-1', found: '7'