67 条题解
-
2
PowderHan LV 10 @ 2017-05-07 13:01:20
/* 好题好题~真心精妙呀~ 第一眼看到这道题是懵逼的根本不知道怎么查询 后来还是想到了拓扑排序但还是不会写 最后看了一下题解~恍然大悟 窝们可以这样做 首先因为每个字母矩形顶角都一定是有的 所以我们可以先求出左上和右下角两个顶角~ 然后就可以确定下这个矩形的形状了 然后窝们沿着四条边扫描一遍 如果有一个字母c在当前字母k矩阵上面 那么说明c一定是在k上面的 那么肯定有在输出顺序中c要在k后面 等等这让窝们想到了什么 有了确定的x在y前面这样的关系 要找到有可能的情况排列 这不就是拓扑排序~！？ 没错我们可以对于满足(c,k)这样条件的两个顶点 从k到c连一条有向边 那么很容易就变成一个求所有拓扑序列的问题了 因为序列要从小到大字典序 而且要输出全部的情况 所以我们考虑dfs即可 dfs还是蛮好写的一个递归然后出口维护还原一下全局变量就好了 即从小到大考虑一个入读为0的点 然后把他删除作为第一个 自然要将他的所有出边对应顶点的入度-- 然后继续递归下去~ 直到找到了一个完整排列(记得统计一下字母个数就好了) */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN=32; char a[MAXN][MAXN]; char ans[MAXN]; int g[MAXN][MAXN]; int in[MAXN]; int h[MAXN]; int n,m; int cnt; void dfs(int cur) { if(cur==cnt) { printf("%s\n",ans); return; } for(int i=0;i<26;i++) if(!in[i]&&h[i]) { ans[cur]=i+'A'; in[i]=-1; for(int j=0;j<26;j++) if(g[i][j]) in[j]--; dfs(cur+1); in[i]=0; for(int j=0;j<26;j++) if(g[i][j]) in[j]++; } } void init() { cin>>n>>m; for(int i=1;i<=n;i++) scanf("%s",a[i]+1); for(int k=0;k<26;k++) { char ch='A'+k; int x1=MAXN; int y1=MAXN; int x2=0; int y2=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]==ch) x1=min(x1,i),y1=min(y1,j), x2=max(x2,i),y2=max(y2,j); if(x1==MAXN||y1==MAXN||x2==0||y2==0) continue; h[k]=1; cnt++; for(int i=x1;i<=x2;i++) for(int j=y1;j<=y2;j++) if(i==x1||i==x2||j==y1||j==y2) if(a[i][j]!=ch&&a[i][j]!='.') { int c=a[i][j]-'A'; if(!g[k][c]) { g[k][c]=1; in[c]++; } } } ans[cnt]='\0'; } int main() { init(); dfs(0); return 0; } -
1
procedure search(x:longint; ch:char);
var ich:char;
begin
st:=ch+st; flag[ch]:=true;
if x=n then begin
inc(c); ans[c]:=st;
end else begin
for ich:='A' to 'Z' do
if f[ch,ich] then dec(d[ich]);
for ich:='A' to 'Z' do
if not flag[ich] and (d[ich]=0) then
search(x+1,ich);
for ich:='A' to 'Z' do
if f[ch,ich] then inc(d[ich]);
end;
delete(st,1,1); flag[ch]:=false;
end; -
0
输入的时候记录多少种字母（多少个图形）
首先预处理，找出每个方框的四个顶点的位置
然后DFS，扫一遍某个方框的四个边，
如果全是该字母或‘0’，则该字母的方框找到，并将方框上的字母替换为0，继续dfs。
如果全部字母找到，记录答案。
最后按照字典序排序，具体操作为：以第K位为关键词，sort升序排序。K：末位to第一位。
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::max;
using std::min;struct qweq{
char a[26];
}ans[1000];int K;
bool cmp(qweq a,qweq b){
return a.a[K]<b.a[K];
}struct qwerty{
int u,d,l,r;
}G[26];int n,m,q=0,map[31][31],find[26]={0};
int ct=0;void dfs(int p[31][31],char found[26],int count){
if(count==q){
ct++;
for(int i=q;i>=1;i--)
ans[ct].a[q-i]=found[i];
ans[ct].a[q]='0';
return;
}
int flag;
int map[31][31];
for(int z=0;z<q;z++){
if(find[z])
continue;
flag=1;
memcpy(map,p,sizeof(map));
for(int x=G[z].l;x<=G[z].r;x++){
char c1=p[G[z].u][x];
char c2=p[G[z].d][x];
flag*=(c1=='A'+z)||(c1=='0');
flag*=(c2=='A'+z)||(c2=='0');
}
for(int x=G[z].u;x<=G[z].d;x++){
char c1=p[x][G[z].l];
char c2=p[x][G[z].r];
flag*=(c1=='A'+z)||(c1=='0');
flag*=(c2=='A'+z)||(c2=='0');
}
if(flag){
found[count+1]='A'+z;
for(int x=G[z].l;x<=G[z].r;x++)
map[G[z].u][x]=map[G[z].d][x]='0';
for(int x=G[z].u;x<=G[z].d;x++)
map[x][G[z].l]=map[x][G[z].r]='0';
find[z]=1;
dfs(map,found,count+1);
find[z]=0;
}}
}int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char c;
scanf(" %c",&c);
map[i][j]=c;
if(c!='.')
q=q>c-'A'?q:c-'A';
}
q++;
for(int i=0;i<q;i++){
G[i].l=31;
G[i].r=0;
G[i].u=31;
G[i].d=0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char c=map[i][j];
if(c=='.')
continue;
int t=c-'A';
G[t].l=min(G[t].l,j);
G[t].r=max(G[t].r,j);
G[t].u=min(G[t].u,i);
G[t].d=max(G[t].d,i);
}
char found[26];
dfs(map,found,0);
for(K=q-1;K>=0;K--)
std::sort(&ans[1],&ans[ct+1],cmp);
for(int i=1;i<=ct;i++){
for(int j=0;j<q;j++)
printf("%c",ans[i].a[j]);
printf("\n");
}return 0;
} -
0
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int MAXN=31; int n,m,in[MAXN],flag[MAXN],cnt=0,M[MAXN][MAXN]; char p[MAXN][MAXN],ans[MAXN]; void dfs(int num) { if(num==cnt) { ans[num]='\0'; printf("%s\n",ans); return ; } for(int i=0;i<26;i++) if(in[i]==0&&flag[i]) { ans[num]=i+'A'; in[i]=-1; for(int j=0;j<26;j++) if(M[i][j])in[j]--; dfs(num+1); in[i]=0; for(int j=0;j<26;j++) if(M[i][j])in[j]++; } } int main() { scanf("%d%d",&n,&m); memset(M,0,sizeof(M)); memset(in,0,sizeof(in)); memset(flag,0,sizeof(flag)); for(int i=0;i<n;i++)scanf("%s",p[i]); for(int k=0;k<26;k++) { int x1=MAXN,y1=MAXN,x2=-1,y2=-1; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(p[i][j]=='A'+k) x1=min(x1,i),y1=min(y1,j),x2=max(x2,i),y2=max(y2,j); if(x1==MAXN||y1==MAXN||x2==-1||y2==-1)continue; flag[k]=1; cnt++; for(int i=x1;i<=x2;i++) for(int j=y1;j<=y2;j++) if(i==x1||i==x2||j==y1||j==y2) if(p[i][j]!='A'+k&&p[i][j]!='.') { int t=p[i][j]-'A'; if(!M[k][t])in[t]++,M[k][t]=1; } } dfs(0); return 0; }DFS+拓扑0ms
-
0
wang_yanheng LV 10 @ 2015-06-27 22:23:37
纯用DFS有些点过不了，估计是细节处理的问题。改用拓扑排序+搜索，秒杀。思路如下：
1. 读入点阵，计算每个方框的边界值
2. 把二维数组 graph 赋0，用来存储转化后的图；把一维数组 in 赋 -1，用来存储每个字母的入度
3. for i='A' to 'Z': 搜索方框 i 的边界，如果任意字母 j != i 出现在边界上，则 graph[i][j]=1 ，且 in[j]++
4. 开始拓扑排序。考虑到有多解，需结合 DFS 的思路，这一部分代码如下：void topoSort(int depth,int maxDepth){
int i,k;
if(depth>=maxDepth){
for(i=0;i<maxDepth;i++)
putchar(path[i]+'A');
putchar('\n');
return;
}
for(i=0;i<26;i++){
if(in[i]==0){
in[i]=-1;
path[depth]=i;
for(k=0;k<26;k++){
if(graph[i][k])
in[k]--;
}
topoSort(depth+1,maxDepth);
in[i]=0;
for(k=0;k<26;k++){
if(graph[i][k])
in[k]++;
}
}
}
}解释说明：maxDepth参数需传入方框的个数，即字母的个数，这一点很容易实现。在 main() 中调用时，depth参数必须为0
-
0
yuyilahanbao LV 10 @ 2013-12-25 20:24:04
测试数据 #0: Accepted, time = 0 ms, mem = 444 KiB, score = 25
测试数据 #1: Accepted, time = 0 ms, mem = 436 KiB, score = 25
测试数据 #2: Accepted, time = 0 ms, mem = 440 KiB, score = 25
测试数据 #3: Accepted, time = 0 ms, mem = 444 KiB, score = 25这道题，首先构造边（关系）。
然后搜索(时间复杂度较高，但是由于数据较范围较小)
具体见代码，函数意思大概看名字能看出来。实在不行看代码。虽然我不确定我的void topology(int d)到底是不是拓扑排序，但是差不多是。虽然可能实现方法较弱，但是大概能实现
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define N 50
#define M 50
#define LN 26
struct matrix{
int t,b,l,r;/*top,botton,left,right*/
};
struct matrix frame[LN+5];
int ln,used[LN],list[LN];
int edge[LN][LN];
int path[LN+5];int n,m;
int main()
{
int i;void init();
void base();
void topology(int d);
void get_list();base();
init();
get_list();
topology(0);return 0;
}int min(int a,int b)
{
if ((a < 0) || (b < a))
return b;
else
return a;
}int max(int a,int b)
{
if (b > a)
return b;
else
return a;
}void set_matric(short a,short r,short c)
{
if (a == '.')
return;
a -= 'A';
if (used[a] == 0)
used[a] = 1;
frame[a].t = min(frame[a].t,r);
frame[a].b = max(frame[a].b,r);
frame[a].l = min(frame[a].l,c);
frame[a].r = max(frame[a].r,c);
}void get_matrix(char s)
{
short r,c;
for (r = 0;r < n;r++) {
for (c = 0;c < m;c++)
set_matric((s+r*M+c),r,c);
}
}void init()
{
char s[N][M];
int i,j;void add_edge(short u,short r,short c);
scanf("%d%d",&n,&m);
for (i = 0;i < n;i++)
scanf("%s",s[i]);
get_matrix(s[0]);
for (i = 0;i < n;i++)
for (j = 0;j < m;j++)
if (s[i][j] != '.')
add_edge(s[i][j]-'A',i,j);
}void base()
{
int i,j;
for (i = 0;i < LN+5;i++)
frame[i].t = frame[i].b = frame[i].l = frame[i].r = -1;
for (i = 0;i < LN;i++)
for (used[i] = j = 0;j < LN;j++)
edge[i][j] = 0;
ln = 0;
}void add_edge(short u,short r,short c)
{
short static v;
for (v = 0;v < LN;v++) {
if ((u == v) || (edge[u][v] == 1) || (edge[v][u] == 1)) continue;
if (((c == frame[v].l) || (c == frame[v].r)) &&
(r >= frame[v].t) && (r <= frame[v].b)) {
edge[u][v] = 1; /*edge[u][v],is frame v under the frame u*/
continue;
}
if (((r == frame[v].b) || (r == frame[v].t)) &&
(c >= frame[v].l) && (c <= frame[v].r))
edge[u][v] = 1; /*edge[u][v],is frame v under the frame u*/
}
}void topology(int d)
{
int v,i,flag;void print();
if (d == ln) {
print(); return;
}
for (v = 0;v < ln;v++) {
if (used[list[v]])
continue;
for (flag = 1,i = 0;i < d && flag;i++)
if (edge[path[i]][list[v]] == 1)
flag = 0;
if (flag) {
used[list[v]] = 1; path[d] = list[v];
topology(d+1);
used[list[v]] = 0;
}
}
return;
}void print()
{
int i;
for (i = 0;i < ln;i++)
printf("%c",path[i]+'A');
printf("\n");
}void get_list()
{
int i,j;
for (ln = i = 0;i < LN;i++)
if (used[i]) {
list[ln++] = i;used[i] = 0;
}
} -
0
yzl609271536 LV 10 @ 2009-11-08 18:05:47
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms犯了低级错误 没想到还有75分
题目不错
纪念 200题-
EXPstar @ 2013-04-29 20:20:11
0ms是什么情况？
-
-
0
sutank2009 LV 8 @ 2009-11-05 08:07:34
先找出有几个方框；
分别分析每一个方框；
{
取出一种字母，就是一个方框；
补齐残缺部分；
补齐之后在原图中的坐标标记；
}
对每一个坐标，若标记的方框数量等于两个，则实际的方框在另一个之上；若标记的方框数量大于两个，则实际的方框在所有的之上；
用一个有向图记录以上所得信息；
g=1表示i不在j之上，即已知j在i之上；
深度优先搜索得出所有解，约束条件g[a[i],a]=1;
Q:如何补齐残缺部分？
A:题目说‘每个方框的4条边都有一部分可见 一个角代表两条边’，由此可以知道补齐残缺部分的办法——从四边由边及里找到第一个出现的字母，即可确定方框的四边;
P.S 这是我编程之前的思考，不知道有没有问题;
-
0
SecretAgent LV 10 @ 2009-10-23 10:34:19
拓扑排序？貌似我没用到。
搜索排列树也没用。。
方法与URAL 1006类似DFS每个字母，
枚举长方形两顶点坐标
若边上不是'*'或者当前字母就跳出。
满足条件就把长方形的边全部改成‘*’号，继续DFS搜完之后给答案排序
程序我就不帖了，5层循环太长太烦琐编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
拓扑排序,就是有点烦,我第一次把i,j打错了,第二次就AC了
-
0
prince_hao LV 10 @ 2009-09-01 20:08:00
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
peng7621260 LV 9 @ 2009-08-29 11:55:41
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms此题乃好题。
PowderHan
LV 10
@ 2017-05-07 13:01:20
