QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#520804 | #5416. Fabulous Fungus Frenzy | wy2025 | TL | 0ms | 3688kb | C++14 | 2.2kb | 2024-08-15 15:54:11 | 2024-08-15 15:54:13 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=22;
int n[N],m[N],k,a[N][N],now[64],mp[N][N][N],cnt[N][64],uy[64];
char op;
struct out{int op,x,y;};
stack<out> ans;
int to_int(char x){
if(isdigit(x)) return x-'0'+1;
if(x>='a'&&x<='z') return x-'a'+11;
return x-'A'+37;
}
bool ck(int o){
int ned=0;
for(int i=1;i<63;i++)
ned+=max(0,cnt[o][i]-now[i]);
return now[63]>=ned;
}
void go(int sx,int sy,int ex,int ey){
while(sx<ex) swap(a[sx][sy],a[sx+1][sy]),ans.push({-3,sx,sy}),sx++;
while(sy<ey) swap(a[sx][sy],a[sx][sy+1]),ans.push({-1,sx,sy}),sy++;
while(sx>ex) swap(a[sx][sy],a[sx-1][sy]),ans.push({-4,sx,sy}),sx--;
while(sy>ey) swap(a[sx][sy],a[sx][sy-1]),ans.push({-2,sx,sy}),sy--;
// cout<<sx<<" "<<sy<<" "<<ex<<" "<<ey<<"\n";
}
void put(int o){
for(int i=1;i<63;i++) uy[i]=min(cnt[o][i],now[i]);
for(int i=1;i<=n[o];i++){
for(int j=1;j<=m[o];j++){
if(a[i][j]==63) continue;
if(a[i][j]==mp[o][i][j]){uy[a[i][j]]--;continue;}
bool f=0;
for(int x=1;x<=n[0];x++){
for(int y=1;y<=m[0];y++){
if(x<=i&&y<=j) continue;
// cout<<x<<" "<<y<<" "<<a[x][y]<<" "<<i<<" "<<j<<" "<<mp[o][i][j]<<"\n";
if(a[x][y]==mp[o][i][j]){go(x,y,i,j),uy[a[x][y]]--,f=1;break;}
if(a[x][y]==63&&!uy[mp[o][i][j]]){go(x,y,i,j),f=1;break;}
}
if(f) break;
}
now[a[i][j]]--,now[63]++;
a[i][j]=63;
}
}
if(o) ans.push({o,1,1});
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n[0]>>m[0]>>k;{
for(int i=1;i<=n[0];i++)
for(int j=1;j<=m[0];j++)
cin>>op,mp[0][i][j]=to_int(op),cnt[0][mp[0][i][j]]++;
for(int i=1;i<=n[0];i++)
for(int j=1;j<=m[0];j++)
cin>>op,a[i][j]=to_int(op),now[a[i][j]]++;
for(int o=1;o<=k;o++){
cin>>n[o]>>m[o];
for(int i=1;i<=n[o];i++)
for(int j=1;j<=m[o];j++)
cin>>op,mp[o][i][j]=to_int(op),cnt[o][mp[o][i][j]]++;
}
}
while(!ck(0)){
bool f=0;
for(int i=1;i<=k;i++)
if(ck(i)) put(i),f=1;
if(!f) cout<<-1,exit(0);
}
put(0);
cout<<ans.size()<<"\n";
while(!ans.empty()) cout<<ans.top().op<<" "<<ans.top().x<<" "<<ans.top().y<<"\n",ans.pop();
return 0;
}
/*
3 3 1
OOO
GOG
BGB
OOO
GGG
BBB
3 1
B
G
B
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3688kb
input:
3 3 1 OOO GOG BGB OOO GGG BBB 3 1 B G B
output:
5 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: 3592kb
input:
2 2 1 OO OO PP PP 1 2 OP
output:
-1
result:
ok puzzle solved
Test #3:
score: -100
Time Limit Exceeded
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