QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#471377#5416. Fabulous Fungus FrenzyzyxawaTL 0ms3896kbC++232.0kb2024-07-10 20:48:572024-07-10 20:48:57

Judging History

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

  • [2024-07-10 20:48:57]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3896kb
  • [2024-07-10 20:48:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define trans(c) (isdigit(c)?c-48:(islower(c)?c-87:c-29))
char ch[21];
vector <tuple<int,int,int>> ans;
int n,m,k,a[21][21],c[21][21][21],h[21],w[21],cnt[63],v[21][21];
int check(int k){
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cnt[a[i][j]]++;
	int res=0;
	for(int i=1;i<=h[k];i++){
		for(int j=1;j<=w[k];j++){
			if(cnt[c[k][i][j]]) cnt[c[k][i][j]]--,res++;
			else if(cnt[0]) cnt[0]--;
			else return -1;
		}
	}
	return res;
}
void solve(int k){
	memset(v,0,sizeof(v));
	for(int i=1;i<=h[k];i++){
		for(int j=1;j<=w[k];j++){
			int x=0,y=0;
			for(int l=1;!x&&l<=n;l++) for(int r=1;r<=m;r++) if(!v[l][r]&&a[l][r]==c[k][i][j]) x=l,y=r;
			if(!x) for(int l=1;!x&&l<=n;l++) for(int r=1;r<=m;r++) if(!v[l][r]&&!a[l][r]) x=l,y=r;
			while(x<i) swap(a[x][y],a[x+1][y]),ans.push_back({-3,x++,y});
			while(y<j) swap(a[x][y],a[x][y+1]),ans.push_back({-1,x,y++});
			while(x>i) swap(a[x][y],a[x-1][y]),ans.push_back({-4,x--,y});
			while(y>j) swap(a[x][y],a[x][y-1]),ans.push_back({-2,x,y--});
			v[i][j]=1;
		}
	}
	int f=0;
	for(int i=1;i<=h[k];i++){
		for(int j=1;j<=w[k];j++){
			f|=a[i][j]!=0;
		}
	}
	if(!f&&k){
		while(1){
			cout<<"SB\n";
		}
	}
	for(int i=1;i<=h[k];i++) for(int j=1;j<=w[k];j++) a[i][j]=0;
	if(k) ans.push_back({k,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",ch+1);
		for(int j=1;j<=m;j++) c[0][i][j]=trans(ch[j]);
	}
	for(int i=1;i<=n;i++){
		scanf("%s",ch+1);
		for(int j=1;j<=m;j++) a[i][j]=trans(ch[j]);
	}
	for(int i=1;i<=k;i++){
		scanf("%d%d",&h[i],&w[i]);
		for(int j=1;j<=h[i];j++){
			scanf("%s",ch+1);
			for(int l=1;l<=w[i];l++) c[i][j][l]=trans(ch[l]);
		}
	}
	while(1){
		if(check(0)>=0) break;
		int f=0;
		for(int i=1;i<=k;i++) if(check(i)>0) f=1,solve(i);
		if(!f) return printf("-1"),0;
	}
	solve(0);
	reverse(begin(ans),end(ans));
	printf("%d\n",ans.size());
	for(auto [a,b,c]:ans) printf("%d %d %d\n",a,b,c);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3864kb

input:

3 3 1
OOO
GOG
BGB

OOO
GGG
BBB

3 1
B
G
B

output:

16
-2 3 3
-2 3 2
-4 3 3
-2 2 3
-2 2 2
-4 2 3
-2 1 3
-2 1 2
-2 1 3
1 1 1
-2 3 2
-2 2 2
-2 1 2
-2 1 3
-4 2 3
-4 3 3

result:

ok puzzle solved

Test #2:

score: 0
Accepted
time: 0ms
memory: 3792kb

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: 3872kb

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:

311
-2 4 8
-2 4 7
-2 4 8
-2 4 6
-2 4 7
-2 4 8
-2 4 5
-2 4 6
-2 4 7
-2 4 8
-2 4 4
-2 4 5
-2 4 6
-2 4 7
-2 4 8
-2 4 3
-2 4 4
-2 4 5
-2 4 6
-2 4 7
-2 4 8
-2 4 2
-2 4 3
-2 4 4
-2 4 5
-2 4 6
-2 4 7
-2 4 8
-2 3 8
-2 3 7
-2 3 8
-2 3 6
-2 3 7
-2 3 8
-2 3 5
-2 3 6
-2 3 7
-2 3 8
-2 3 4
-2 3 5
-2 3 6
-2 3 7
-2...

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:

8
-2 2 2
-2 1 2
-4 2 2
1 1 1
-4 2 1
1 1 1
-4 2 2
-2 1 2

result:

ok puzzle solved

Test #5:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

2 2 1
OO
OO

OP
PO

2 1
P
P

output:

5
-2 2 2
-4 2 2
-2 1 2
1 1 1
-2 1 2

result:

ok puzzle solved

Test #6:

score: 0
Accepted
time: 0ms
memory: 3888kb

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: 3760kb

input:

2 2 1
OO
OO

OP
PP

1 2
OP

output:

10
-2 2 2
-2 1 2
1 1 1
-4 2 2
-1 2 1
-2 1 2
1 1 1
-4 2 2
-2 1 2
1 1 1

result:

ok puzzle solved

Test #8:

score: -100
Time Limit Exceeded

input:

20 20 20
bofelagiqboebdqplbhq
qsrksfthhptcmikjohkt
qrnhpoatbekggnkdonet
aoalekbmpbisgflbhmol
djnhnlitcakltqgegqrt
fdctfarsmbnbeosdgilo
ttrsljgiratfmioajorh
gorljkihdnmnofnblfhm
bqjkaehetdjlgctmijpc
geslcskpoqjcgtbdspoa
riqthroqmmhqgprqhsba
fdiarrcomockfqdjjdkd
jsbnigfqgsfekbbnnkir
ildqctqtqrpcetaocp...

output:

SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
SB
...

result: