QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293843#5416. Fabulous Fungus FrenzyhuzhaoyangWA 1ms3756kbC++142.0kb2023-12-29 20:52:172023-12-29 20:52:17

Judging History

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

  • [2023-12-29 20:52:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3756kb
  • [2023-12-29 20:52:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=25,M=100;
int n,m,k,cnt[M];
char s[N][N];
vector<pair<int,pair<int,int> > >ans;
int get(char c){
	if (c=='?')return 62;
	if (c<='9')return c-'0';
	if (c<='Z')return c-'A'+10;
	return c-'a'+36;
}
struct Matrix{
	int n,m,cnt[M];
	char s[N][N];
	void init(){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)cnt[get(s[i][j])]++;
	}
}a[N];
void swapD(int x,int y){
	swap(s[x][y],s[x+1][y]);
	ans.push_back(make_pair(-3,make_pair(x,y)));
}
void swapR(int x,int y){
	swap(s[x][y],s[x][y+1]);
	ans.push_back(make_pair(-1,make_pair(x,y)));
}
bool check(int k){
	int s=0;
	for(int i=0;i<62;i++)s+=max(a[k].cnt[i]-cnt[i],0);
	if (s>cnt[62])return 0;
	for(int i=0;i<62;i++)
		if ((a[k].cnt[i])&&(cnt[i]))return 1;
	return 0;
}
void calc(int k){
	for(int i=1;i<=a[k].n;i++)
		for(int j=1;j<=a[k].m;j++){
			int c=get(a[k].s[i][j]);
			if (!cnt[c])c=62;
			for(int x=1;x<=n;x++)
				for(int y=1;y<=m;y++)
					if ((get(s[x][y])==c)&&((x>i)||(x==i)&&(y>=j))){
						while (x<i)swapD(x++,y);
						while (y<j)swapR(x,y++);
						while (x>i)swapD(--x,y);
						while (y>j)swapR(x,--y);
						x=y=114514;
					}
			s[i][j]='?',cnt[c]--,cnt[62]++;
		}
	if (k)ans.push_back(make_pair(k,make_pair(1,1)));
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	a[0].n=n,a[0].m=m;
	for(int i=1;i<=n;i++)scanf("%s",a[0].s[i]+1);
	for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
	for(int t=1;t<=k;t++){
		scanf("%d%d",&a[t].n,&a[t].m);
		for(int i=1;i<=a[t].n;i++)scanf("%s",a[t].s[i]+1);
	}
	for(int t=0;t<=k;t++)a[t].init();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)cnt[get(s[i][j])]++;
	while (1){
		if (check(0)){
			calc(0);
			break;
		}
		bool flag=0;
		for(int t=1;t<=k;t++)
			if (check(t))flag=1,calc(t);
		if (!flag){
			puts("-1");
			return 0;
		}
	}
	printf("%d\n",ans.size());
	reverse(ans.begin(),ans.end());
	for(pair<int,pair<int,int> >i:ans)printf("%d %d %d\n",i.first,i.second.first,i.second.second);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3592kb

input:

3 3 1
OOO
GOG
BGB

OOO
GGG
BBB

3 1
B
G
B

output:

13
-1 3 1
-3 2 3
-1 3 2
-1 2 1
-3 1 3
-1 2 2
-1 1 2
-1 1 1
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: 1ms
memory: 3756kb

input:

2 2 1
OO
OO

PP
PP

1 2
OP

output:

-1

result:

ok puzzle solved

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3536kb

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:

-1

result:

wrong answer solvable puzzle unsolved