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 张牌，排成 nn 行 mm 列的矩阵。由于是从一副牌中取的，保证互不相同。你需要将“王”替换成任意没出现过的普通牌，然后判断能否找到两个不重叠的 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;
}