QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#520807#5416. Fabulous Fungus FrenzyzTL 2ms4072kbC++142.2kb2024-08-15 15:59:102024-08-15 15:59:11

Judging History

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

  • [2024-08-15 15:59:11]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:4072kb
  • [2024-08-15 15:59:10]
  • 提交

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;
}

詳細信息

Test #1:

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

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

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

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

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

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

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

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

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

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...

output:


result: