QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#520821 | #5416. Fabulous Fungus Frenzy | z | TL | 2ms | 4132kb | C++23 | 2.2kb | 2024-08-15 16:05:32 | 2024-08-15 16:05:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=22,M=100;
char S[N];
int step;
int n,m,k;
int s[N][N][N];
int a[N][N];
int h[N],w[N];
int col[M];
struct Opt{
int op,x,y;
}O[400005];
int trans(char c){
if(c>96) return c-86;
if(c>64) return c-28;
return c-47;
}
int check(int x){
for(int i=0;i<=62;i++) col[i]=0;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) col[a[i][j]]++;
int v=0;
for(int i=1;i<=h[x];i++)
for(int j=1;j<=w[x];j++){
if(col[s[x][i][j]]) --col[s[x][i][j]],++v;
else if(col[0]) --col[0];
else return -1;
}
return v;
}
char tr(int x){
if(x<11) return x+47;
if(x<37) return x+86;
return x+28;
}
void solve(int now){
for(int i=1;i<=h[now];i++){
for(int j=1;j<=w[now];j++){
int x=0,y=0;
for(int p=1;!x&&p<=n;p++) for(int q=1;!x&&q<=m;q++)
if((p>i||p<i&&q>w[x]||p==i&&q>=j)&&a[p][q]==s[now][i][j]) x=p,y=q;
for(int p=1;!x&&p<=n;p++) for(int q=1;!x&&q<=m;q++)
if((p>i||p<i&&q>w[x]||p==i&&q>=j)&&a[p][q]==0) x=p,y=q;
//下左右上
while(x<i) swap(a[x][y],a[x+1][y]),O[++step]={-3,x,y},++x;
while(y>j) swap(a[x][y],a[x][y-1]),O[++step]={-2,x,y},--y;
while(y<j) swap(a[x][y],a[x][y+1]),O[++step]={-1,x,y},++y;
while(x>i) swap(a[x][y],a[x-1][y]),O[++step]={-4,x,y},--x;
a[i][j]=0;
}
}
O[++step]={now,1,1};
}
int main(){
scanf("%d%d%d",&n,&m,&k);
h[0]=n,w[0]=m;
for(int i=1;i<=n;i++){
scanf("%s",S+1);
for(int j=1;j<=m;j++)
s[0][i][j]=trans(S[j]);
}
for(int i=1;i<=n;i++){
scanf("%s",S+1);
for(int j=1;j<=m;j++)
a[i][j]=trans(S[j]);
}
for(int l=1;l<=k;l++){
scanf("%d%d",&h[l],&w[l]);
for(int i=1;i<=h[l];i++){
scanf("%s",S+1);
for(int j=1;j<=w[l];j++)
s[l][i][j]=trans(S[j]);
}
}
while(1){
bool f=1;
if(check(0)>=0) break;
for(int i=1;i<=k;i++){
if(check(i)>0){
solve(i);
f=0;
}
}
if(f){
puts("-1");
return 0;
}
}
solve(0);
printf("%d\n",step-1);
for(int i=step-1;i;i--) printf("%d %d %d\n",O[i].op,O[i].x,O[i].y);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3944kb
input:
3 3 1 OOO GOG BGB OOO GGG BBB 3 1 B G B
output:
13 -2 3 2 -4 3 3 -1 3 2 -2 2 2 -4 2 3 -1 2 2 -2 1 3 -2 1 2 1 1 1 -2 3 2 -2 2 2 -4 2 1 -4 3 1
result:
ok puzzle solved
Test #2:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
2 2 1 OO OO PP PP 1 2 OP
output:
-1
result:
ok puzzle solved
Test #3:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
4 8 4 11122222 33344444 55556666 77777777 NIxSHUOx DExDUIxx DANxSHIx YUANSHEN 2 3 NIy DEx 3 8 zzzzzzzz DANNSH9I YUA9SHEN 1 1 x 2 5 SHO8y DUUI8
output:
165 3 1 1 -4 2 1 -4 3 1 -4 4 1 -2 4 2 -2 4 3 -2 4 4 -2 4 5 -2 4 6 -2 4 7 -2 4 8 1 1 1 -4 3 3 -4 4 3 -2 4 4 -2 4 5 -2 4 6 3 1 1 -4 2 1 -4 3 1 -4 4 1 -2 4 2 -2 4 3 -2 4 4 2 1 1 -4 4 8 -1 4 7 -1 4 6 -1 4 5 -1 4 4 -1 4 3 -1 4 2 -1 4 1 -4 4 7 -1 4 6 -1 4 5 -1 4 4 -1 4 3 -1 4 2 -1 4 1 -4 4 6 -2 4 7 -2 4 8...
result:
ok puzzle solved
Test #4:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
2 2 1 OO OO OP PP 1 2 PP
output:
8 -4 2 1 -2 2 2 1 1 1 -4 2 1 1 1 1 -4 2 2 -1 2 1 -2 1 2
result:
ok puzzle solved
Test #5:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
2 2 1 OO OO OP PO 2 1 P P
output:
4 -4 2 2 -2 1 2 1 1 1 -2 1 2
result:
ok puzzle solved
Test #6:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
2 2 1 OO OO OP PO 2 2 PP PP
output:
-1
result:
ok puzzle solved
Test #7:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
2 2 1 OO OO OP PP 1 2 OP
output:
7 1 1 1 -4 2 2 -1 2 1 1 1 1 -4 2 2 -1 2 1 1 1 1
result:
ok puzzle solved
Test #8:
score: 0
Accepted
time: 2ms
memory: 4132kb
input:
20 20 20 bofelagiqboebdqplbhq qsrksfthhptcmikjohkt qrnhpoatbekggnkdonet aoalekbmpbisgflbhmol djnhnlitcakltqgegqrt fdctfarsmbnbeosdgilo ttrsljgiratfmioajorh gorljkihdnmnofnblfhm bqjkaehetdjlgctmijpc geslcskpoqjcgtbdspoa riqthroqmmhqgprqhsba fdiarrcomockfqdjjdkd jsbnigfqgsfekbbnnkir ildqctqtqrpcetaocp...
output:
9694 8 1 1 -4 2 1 -4 3 1 -4 4 1 -4 5 1 -4 6 1 -4 7 1 -4 8 1 -4 9 1 -4 10 1 -4 11 1 -4 12 1 -4 13 1 -4 14 1 -4 15 1 -4 16 1 -4 17 1 -4 18 1 -4 19 1 -4 20 1 -2 20 2 -2 20 3 -2 20 4 -2 20 5 -2 20 6 -2 20 7 -2 20 8 -2 20 9 -2 20 10 -2 20 11 -2 20 12 -2 20 13 -2 20 14 -2 20 15 -2 20 16 -2 20 17 -2 20 18 ...
result:
ok puzzle solved
Test #9:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
20 20 2 HbevPluVL5ORtUFcV9gf Mrq6zdTPMPnwlN7Fpzx6 Nfp71dVuxTZp9Qet0Ca9 ugbaF34DquDdbUnk5x7V fDFszn4PmvMpJ5BDWueJ 2YvFxKJgst8XbftPfy9T F7Q4huk87Lrp1M7i08is Q41E5AqLkkP3Q5qONXC2 MuM7iIzev3ZpxItvriQK 6OBdEC0sso5vdNQlrCSR BJQtKjN6RmppsMGIYL81 yyKsWJSoKorGGblNle0r RkKEQACh8f0bS5nPTtJH fQgoc39vdsPAUmxlYYL...
output:
-1
result:
ok puzzle solved
Test #10:
score: -100
Time Limit Exceeded
input:
20 20 2 pqo3Mcpvo74RFSsJszsa znrYm92Qr8fbqhbCTOgq 4KiMYr0kLAxPGNG15x7L QHKmq6xaJ4PU4msuRAiv UBfS6VUO87hRnMAjGXKX zCgknw3FfhdifmVcT6FF GH6ohIAzZuprlC3vMDVh mHIJ9KlQvWxt6EgGbJkA 3SwJNhRSdEeF9BNtc9k2 mZmEuriH7Rc4ccMjqI0Y cFfI8TC1iM4PkKziLOiN 15CUjuwudnrums3c3dsl ekL52LiFEpzmU4vaGtuX CfrnQtWb5zAN9oQS2fj...