MYF

2016弱校连萌Round 1a Abstract Picture

题目链接

Abstract Picture

方法: 搜索

题目分析

题目大意

给定一个n*n的画板,上面一个字符代表一个颜色。每一个格子会刷两次,一次横着刷,一次竖着刷,后刷的颜色会覆盖先刷的颜色,问号表示不关心这个位置的颜色,打印出一种方案,形成这样的画板。

解析

最后一次刷一定会形成一行或者一列,使这一行或一列一定是一个颜色,所以,以此作为突破口。初级想法是这样的,先找到最后一次刷的那一行或者那一列,然后把这一行或者这一列全部刷成?,然后再暴力横着扫n次,竖着扫n次,直到扫不出来为止,然而这个会T。中级想法是这样的,加入剪枝,如果这一行或这一列扫过,设置一个vis[]数组,如果再次循环扫到这个位置,直接continue跳过,然而这个也不可以,到35发会T。最终的想法是这样的,也是看了学长的代码学到的,敲了n遍,debug花了半天。建立两个set统计每一行的有哪些字符,每一列有哪些字符。建立两个cnt[maxn][26]表示每一行,每一列中每个字符出现的次数,先扫一遍,找到找到集合中只有一个字符或没有的那一行或者那一列,加入队列中。然后对队列中的每一个元素扫描。如果队首元素表示扫描这一行,则对这一行的每一个元素所在的每一列找到这个元素的统计,好吧说的很绕,其实就是cntH[i][mp[i][now]-'a'],如果这个元素递减之后等于零,则查看当前这一列的set,如果元素个数小于等于一,则把当前列标记访问,加入答案的数组里,然后加入队列。

收获

再也不用宏定义了

#define maxn 3000+50这个东西,当我定义了ans[2*maxn];表示的是ans[2*3000+5;也就是ans[6005],但是ans[maxn*2];表示的却是ans[3000+5*2];也就是ans[3010];所以说,这一次又体会到了宏定义是一种不安全的定义方式,以后头文件里不用这个东西了。

移位标记方式

本来看到位运算就头晕,今天看到学长将入队的那个数进行一些操作,达到一种标记操作的目的。比如操作的值为x,我对x总共有7种操作方式,那么我可以使用7*x来表示第一种操作方式7*x+1表示第二种操作方式,然后等出队的时候,使用now%7即可知道应该对当前的这个元素进行那一个操作,使用now/7即可表示原值。

代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n) (j == n ? '\n' : ' ')
#define hi printf("Hi----------\n")
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 3000+50
#define mod 1000000007
int n,cnt=0;
int visV[maxn]={},visH[maxn]={};
int cntV[maxn][30]={},cntH[maxn][30]={};
char mp[maxn][maxn]={};
set<char> stV[maxn],stH[maxn];
queue<int>q;
struct node{
char c,d;
int p;
node(){}
node(char dir,int pos, char col):d(dir),p(pos),c(col){}
}ans[2*maxn];
int main(){
scanf("%d",&n);
for (int i=1; i<=n; i++) {
scanf("%s",mp[i]+1);
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (mp[i][j]!='?') {
stH[i].insert(mp[i][j]);
stV[j].insert(mp[i][j]);
cntH[i][mp[i][j]-'a']++;
cntV[j][mp[i][j]-'a']++;
}
}
}
for (int i=1; i<=n; i++) {
if (stH[i].size()<=1) {
visH[i]=1;
q.push(i<<1|1);
char ch='a';
if (stH[i].size()) {
ch=*stH[i].begin();
}
ans[cnt++]=node('h', i, ch);
}
if (stV[i].size()<=1) {
visV[i]=1;
q.push(i<<1);
char ch='a';
if (stV[i].size()) {
ch=*stV[i].begin();
}
ans[cnt++]=node('v', i, ch);
}
}
while (!q.empty()) {
int now=q.front();q.pop();
int dir=(now&1);
now>>=1; //移位标记的方式
if (dir) {
//横着扫
for (int i=1; i<=n; i++) {
if (!visV[i]&&mp[now][i]!='?') {
if (--cntV[i][mp[now][i]-'a']==0) {
stV[i].erase(mp[now][i]);
if (stV[i].size()<=1) {
q.push(i<<1);
char ch='a';
if (stV[i].size()) {
ch=*stV[i].begin();
}
visV[i]=1;
ans[cnt++]=node('v', i, ch);
}
}
}
}
}
else{
//竖着扫
for (int i=1; i<=n; i++) {
if (!visH[i]&&mp[i][now]!='?') {
if (--cntH[i][mp[i][now]-'a']==0) {
stH[i].erase(mp[i][now]);
if (stH[i].size()<=1) {
q.push(i<<1|1);
visH[i]=1;
char ch='a';
if (stH[i].size()) {
ch=*stH[i].begin();
}
ans[cnt++]=node('h', i, ch);
}
}
}
}
}
}
for (int i=cnt-1; i>=0; i--) {
printf("%c %d %c\n",ans[i].d,ans[i].p,ans[i].c);
}
return 0;
}