QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#520804#5416. Fabulous Fungus Frenzywy2025TL 0ms3688kbC++142.2kb2024-08-15 15:54:112024-08-15 15:54:13

Judging History

你现在查看的是最新测评结果

  • [2024-08-15 15:54:13]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3688kb
  • [2024-08-15 15:54:11]
  • 提交

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

output:


result: