QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#510539 | #5416. Fabulous Fungus Frenzy | xiahaob | TL | 2ms | 5812kb | C++14 | 2.2kb | 2024-08-09 09:05:44 | 2024-08-09 09:05:46 |
Judging History
answer
#include<bits/stdc++.h>
#define eb(a,b,c) emplace_back(a,b,c)
using namespace std;
inline int rd(){
int s=0,w=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')w=-1;
for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0';
return s*w;
}
char FF[100];
int n[100],m[100],k;
int S[100][100][100],T[100][100],cs[100][100],ct[100];
vector<tuple<int,int,int> > opt;
inline int STR(char ch){
if(isdigit(ch))return ch-'0';
if(islower(ch))return 10+ch-'a';
return 36+ch-'A';
}
inline void TO(int x,int y,int a,int b,int id){//s,t
for(;y<m[id];++y)opt.eb(-2,x,y+1),swap(T[x][y],T[x][y+1]);
for(;y>m[id];--y)opt.eb(-1,x,y-1),swap(T[x][y],T[x][y-1]);
for(;x>a;--x)opt.eb(-3,x-1,y),swap(T[x][y],T[x-1][y]);
for(;x<a;++x)opt.eb(-4,x+1,y),swap(T[x][y],T[x+1][y]);
for(;y>b;--y)opt.eb(-1,x,y-1),swap(T[x][y],T[x][y-1]);
}
inline bool rev(int id){
int sm=0;
for(int i=0;i<62;++i)sm+=min(cs[id][i],ct[i]);
if(sm+ct[62]<n[id]*m[id]||(!sm&&id))return 0;
for(int i=1;i<=n[id];++i){
for(int j=1;j<=m[id];++j){
int x=0,y=0;
for(int a=i;a<=n[0];++a){
for(int b=(a==i?j:1);b<=m[0];++b)if(S[id][i][j]==T[a][b]){x=a;y=b;break;}
if(x)break;
}
if(!x){
for(int a=i;a<=n[0];++a){
for(int b=(a==i?j:1);b<=m[0];++b)if(T[a][b]==62){x=a;y=b;break;}
if(x)break;
}
}
TO(x,y,i,j,id);
}
}
if(id)opt.eb(id,1,1);
for(int i=1;i<=n[id];++i)for(int j=1;j<=m[id];++j)ct[T[i][j]]--,ct[T[i][j]=62]++;
return 1;
}
int main(){
n[0]=rd();m[0]=rd();k=rd();
for(int i=1;i<=n[0];++i){
scanf("%s",FF+1);
for(int j=1;j<=m[0];++j)S[0][i][j]=STR(FF[j]),cs[0][S[0][i][j]]++;
}
for(int i=1;i<=n[0];++i){
scanf("%s",FF+1);
for(int j=1;j<=m[0];++j)T[i][j]=STR(FF[j]),ct[T[i][j]]++;
}
for(int z=1;z<=k;++z){
n[z]=rd();m[z]=rd();
for(int i=1;i<=n[z];++i){
scanf("%s",FF+1);
for(int j=1;j<=m[z];++j)S[z][i][j]=STR(FF[j]),cs[z][S[z][i][j]]++;
}
}
while(1){
bool flag=0;
for(int i=1;i<=k;++i)flag|=rev(i);
if(!flag)break;
}
if(!rev(0))return puts("-1"),0;
reverse(opt.begin(),opt.end());
printf("%d\n",opt.size());
for(auto [x,y,z]:opt)printf("%d %d %d\n",x,y,z);
return 0;
}
/*
3 3 1
OOO
GOG
BGB
OOO
GGG
BBB
3 1
B
G
B
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
input:
3 3 1 OOO GOG BGB OOO GGG BBB 3 1 B G B
output:
33 -1 3 2 -2 3 3 -1 3 1 -1 3 2 -2 3 3 -2 3 2 -1 2 2 -2 2 3 -1 2 1 -1 2 2 -2 2 3 -2 2 2 -3 1 3 -1 1 2 -1 1 1 -1 1 2 -2 1 3 1 1 1 -3 2 1 -1 3 1 -1 3 2 1 1 1 -1 2 1 -1 2 2 -3 1 1 -3 2 1 -1 3 1 -1 3 2 1 1 1 -1 3 1 -1 2 1 -3 1 1 -3 2 1
result:
ok puzzle solved
Test #2:
score: 0
Accepted
time: 0ms
memory: 3820kb
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: 3920kb
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:
535 -1 4 7 -2 4 8 -1 4 6 -1 4 7 -2 4 8 -2 4 7 -1 4 5 -1 4 6 -1 4 7 -2 4 8 -2 4 7 -2 4 6 -1 4 4 -1 4 5 -1 4 6 -1 4 7 -2 4 8 -2 4 7 -2 4 6 -2 4 5 -1 4 3 -1 4 4 -1 4 5 -1 4 6 -1 4 7 -2 4 8 -2 4 7 -2 4 6 -2 4 5 -2 4 4 -1 4 2 -1 4 3 -1 4 4 -1 4 5 -1 4 6 -1 4 7 -2 4 8 -2 4 7 -2 4 6 -2 4 5 -2 4 4 -2 4 3 -1...
result:
ok puzzle solved
Test #4:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
2 2 1 OO OO OP PP 1 2 PP
output:
13 -1 2 1 -2 2 2 -1 1 1 -3 1 2 -2 2 2 1 1 1 -1 1 1 -3 1 2 -2 2 2 1 1 1 -3 1 2 -2 2 2 -1 1 1
result:
ok puzzle solved
Test #5:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
2 2 1 OO OO OP PO 2 1 P P
output:
6 -1 2 1 -2 2 2 -3 1 2 -1 1 1 1 1 1 -1 1 1
result:
ok puzzle solved
Test #6:
score: 0
Accepted
time: 0ms
memory: 3836kb
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: 3896kb
input:
2 2 1 OO OO OP PP 1 2 OP
output:
17 -1 2 1 -2 2 2 -1 1 1 -2 1 2 1 1 1 -3 1 2 -2 2 2 -1 1 1 -2 1 2 1 1 1 -3 1 2 -2 2 2 -1 1 1 -2 1 2 1 1 1 -1 1 1 -2 1 2
result:
ok puzzle solved
Test #8:
score: 0
Accepted
time: 2ms
memory: 4108kb
input:
20 20 20 bofelagiqboebdqplbhq qsrksfthhptcmikjohkt qrnhpoatbekggnkdonet aoalekbmpbisgflbhmol djnhnlitcakltqgegqrt fdctfarsmbnbeosdgilo ttrsljgiratfmioajorh gorljkihdnmnofnblfhm bqjkaehetdjlgctmijpc geslcskpoqjcgtbdspoa riqthroqmmhqgprqhsba fdiarrcomockfqdjjdkd jsbnigfqgsfekbbnnkir ildqctqtqrpcetaocp...
output:
17294 -1 20 19 -2 20 20 -1 20 18 -1 20 19 -2 20 20 -2 20 19 -1 20 17 -1 20 18 -1 20 19 -2 20 20 -2 20 19 -2 20 18 -1 20 16 -1 20 17 -1 20 18 -1 20 19 -2 20 20 -2 20 19 -2 20 18 -2 20 17 -1 20 15 -1 20 16 -1 20 17 -1 20 18 -1 20 19 -2 20 20 -2 20 19 -2 20 18 -2 20 17 -2 20 16 -1 20 14 -1 20 15 -1 20 ...
result:
ok puzzle solved
Test #9:
score: 0
Accepted
time: 1ms
memory: 5812kb
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...