CF71D. Solitaire题解

题目传送门

题意:一副扑克牌由 54 张牌组成,包括 52 张基本牌和两张“王”。在本题中每张牌用两个字符表示:

  • 对于基本牌,第一个字符为点数,有 '2' '3' '4' '5' '6' '7' '8' '9' 'T' 'J' 'Q' 'K' 'A' 13 种;第二个字符为花色,有 'C' 'D' 'H' 'S' 四种。
  • 两张“王”分别用 "J1" "J2" 表示。

现在你有 n×mn\times m 张牌,排成 nnmm 列的矩阵。由于是从一副牌中取的,保证互不相同。你需要将“王”替换成任意没出现过的普通牌,然后判断能否找到两个不重叠3×33\times 3 的正方形,使得这两个正方形各自都满足以下条件:要么花色全部相同,要么点数互不相同

一个模拟题。枚举两张王替换成什么(可以使用 DFS 递归两步,注意必须没出现过),然后判断局面是否可行。具体地,判断时,枚举两个位置,判断不重叠且花色相同/点数不同。可以使用 set 去重的集合大小来简化代码。

By cxm1024

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
char t1[14]="23456789TJQKA";
char t2[5]="CDHS";
bool vis[13][4],ok[20][20],hav[128];
char a[20][20][3];
int n,m,x[3],y[3];
pair<PII,PII> check() {
memset(ok,0,sizeof(ok));
rep(i,1,n-2) rep(j,1,m-2) {
set<char> s1,s2;
rep(dx,0,2) rep(dy,0,2) {
s1.insert(a[i+dx][j+dy][0]);
s2.insert(a[i+dx][j+dy][1]);
}
ok[i][j]=(s1.size()==9||s2.size()==1);
}
rep(i1,1,n-2) rep(j1,1,m-2)
rep(i2,1,n-2) rep(j2,1,m-2) {
if(abs(j1-j2)<3&&abs(i1-i2)<3) continue;
if(ok[i1][j1]&&ok[i2][j2])
return {{i1,j1},{i2,j2}};
}
return {{-1,-1},{-1,-1}};
}
void print(pair<PII,PII> ans) {
if(ans.first.first==-1) return;
puts("Solution exists.");
if(x[1]==0&&x[2]==0) puts("There are no jokers.");
else if(x[1]&&x[2]) printf("Replace J1 with %s and J2 with %s.\n",a[x[1]][y[1]],a[x[2]][y[2]]);
else printf("Replace J%d with %s.\n",(x[1]==0?2:1),a[x[1]+x[2]][y[1]+y[2]]);
printf("Put the first square to (%d, %d).\n",ans.first.first,ans.first.second);
printf("Put the second square to (%d, %d).\n",ans.second.first,ans.second.second);
exit(0);
}
void dfs(int now) {
if(now==3) print(check());
else if(x[now]==0) dfs(now+1);
else {
rep(i,0,12) rep(j,0,3) {
if(vis[i][j]) continue;
a[x[now]][y[now]][0]=t1[i];
a[x[now]][y[now]][1]=t2[j];
vis[i][j]=1;
dfs(now+1);
vis[i][j]=0;
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) {
scanf("%s",a[i][j]);
if(a[i][j][0]=='J'&&a[i][j][1]=='1') x[1]=i,y[1]=j;
else if(a[i][j][0]=='J'&&a[i][j][1]=='2') x[2]=i,y[2]=j;
else {
int p,q;
rep(k,0,12) if(a[i][j][0]==t1[k]) p=k;
rep(k,0,3) if(a[i][j][1]==t2[k]) q=k;
vis[p][q]=1;
}
}
dfs(1);
puts("No solution.");
return 0;
}