QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #817385 | #3128. Rush Hour Puzzle | SGColin | AC ✓ | 76ms | 3952kb | C++20 | 2.6kb | 2024-12-16 22:04:36 | 2024-12-16 22:04:36 |
Judging History
answer
#include<bits/stdc++.h>
#include<map>
using namespace std;
#define ll long long
const int N=15;
unordered_map<ll,int>mmp;
int a[N][N];
int lx[11],rx[11],dy[11],uy[11];
int ans,n;
void dfs(int k)
{
if(k+(uy[1]-dy[1]+1)>ans)return;
// cout<<uy[1]<<endl;
if(uy[1]==6){
ans=k+(uy[1]-dy[1]+1);
return;
}
if(k+(uy[1]-dy[1]+1)>=10)return;
ll vist=0;
for(int i=1;i<=10;i++){
if(lx[i]==rx[i])vist=vist*11+dy[i];
else vist=vist*11+lx[i];
}
// cout<<k<<' '<<vist<<' '<<ans<<endl;
// for(int i=1;i<=6;i++){
// for(int j=1;j<=6;j++)
// cout<<a[i][j]<<' ';
// cout<<endl;
// }
// cout<<endl;
// system("pause");
if(mmp[vist]){
if(mmp[vist]<k+1)return;
}
mmp[vist]=k+1;
for(int i=1;i<=n;i++){
if(dy[i]>uy[i]||lx[i]>rx[i])continue;
int x,y;
if(dy[i]!=uy[i]){
int x=dy[i],y=uy[i];
for(int j=x;j<=y;j++)
a[lx[i]][j]=0;
bool vis=true;
for(int j=1;j<2&&vis;j++){
if(a[lx[i]][x-j]!=0){
vis=false;
continue;
}
for(int k=x;k<=y;k++)
a[lx[i]][k-j]=i;
dy[i]=x-j,uy[i]=y-j;
dfs(k+1);
for(int k=x;k<=y;k++)
a[lx[i]][k-j]=0;
}
vis=true;
for(int j=1;j<2&&vis;j++){
if(a[lx[i]][y+j]!=0){
vis=false;
continue;
}
for(int k=x;k<=y;k++)
a[lx[i]][k+j]=i;
dy[i]=x+j,uy[i]=y+j;
dfs(k+1);
for(int k=x;k<=y;k++)
a[lx[i]][k+j]=0;
}
dy[i]=x,uy[i]=y;
for(int k=x;k<=y;k++)
a[lx[i]][k]=i;
}else if(lx[i]!=rx[i]){
int x=lx[i],y=rx[i];
for(int j=x;j<=y;j++)
a[j][dy[i]]=0;
bool vis=true;
for(int j=1;j<2&&vis;j++){
if(a[x-j][dy[i]]!=0){
vis=false;
continue;
}
for(int k=x;k<=y;k++)
a[k-j][dy[i]]=i;
lx[i]=x-j,rx[i]=y-j;
dfs(k+1);
for(int k=x;k<=y;k++)
a[k-j][dy[i]]=0;
}
vis=true;
for(int j=1;j<2&&vis;j++){
if(a[y+j][dy[i]]!=0){
vis=false;
continue;
}
for(int k=x;k<=y;k++)
a[k+j][dy[i]]=i;
lx[i]=x+j,rx[i]=y+j;
dfs(k+1);
for(int k=x;k<=y;k++)
a[k+j][dy[i]]=0;
}
lx[i]=x,rx[i]=y;
for(int k=x;k<=y;k++)
a[k][dy[i]]=i;
}
}
}
int main()
{
ans=10000;
for(int i=1;i<=10;i++)
lx[i]=dy[i]=9,rx[i]=uy[i]=0;
for(int i=1;i<=6;i++)
a[0][i]=a[i][0]=a[7][i]=a[i][7]=-1;
for(int i=1;i<=6;i++){
for(int j=1;j<=6;j++){
scanf("%d",&a[i][j]);
int t=a[i][j];
lx[t]=min(i,lx[t]);
rx[t]=max(i,rx[t]);
dy[t]=min(j,dy[t]);
uy[t]=max(j,uy[t]);
n=max(n,t);
}
}
dfs(0);
if(ans>10){
ans=-1;
}
printf("%d",ans);
}
/*
0 3 3 10 9 9
0 0 2 10 0 8
1 1 2 0 0 8
0 0 4 4 0 7
0 5 5 0 0 7
0 0 0 6 6 7
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 3808kb
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: 0ms
memory: 3872kb
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: 1ms
memory: 3748kb
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: 76ms
memory: 3904kb
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: 7ms
memory: 3808kb
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: 0ms
memory: 3824kb
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: 3808kb
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: 0
Accepted
time: 32ms
memory: 3856kb
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:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
5 4 4 3 3 3 5 0 0 0 0 2 5 0 0 1 1 2 6 0 0 0 0 9 6 0 0 0 0 9 7 7 8 8 8 0
output:
10
result:
ok single line: '10'
Test #10:
score: 0
Accepted
time: 18ms
memory: 3952kb
input:
0 0 5 5 5 0 2 0 6 6 0 0 2 1 1 0 8 0 0 0 0 0 8 7 0 3 3 0 0 7 0 0 0 4 4 0
output:
6
result:
ok single line: '6'
Test #11:
score: 0
Accepted
time: 19ms
memory: 3856kb
input:
0 0 0 0 2 2 0 0 0 0 3 4 1 1 0 0 3 4 0 0 0 0 3 0 0 0 0 0 5 5 0 0 0 6 6 6
output:
-1
result:
ok single line: '-1'
Test #12:
score: 0
Accepted
time: 9ms
memory: 3884kb
input:
2 2 2 0 0 3 0 0 4 0 0 3 1 1 4 0 0 3 0 5 0 0 6 6 7 5 0 0 8 8 7 5 0 0 0 0
output:
-1
result:
ok single line: '-1'