题解

67 条题解

  • 2
    @ 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;
    }
         
    
  • 0
    @ 2018-01-07 11:35:57

    我看了各位大佬的终于算是ac了。。真的好折磨哦。。
    这道题我感觉第一步求的应该就是那个框框的位置就是它的坐标
    第二步就是统计框框边上的不是它本身的字母建立 拓扑
    第三部就是找入度为0的不停的算出排序

  • 0
    @ 2016-08-20 12:54:18

    输入的时候记录多少种字母(多少个图形)
    首先预处理,找出每个方框的四个顶点的位置
    然后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
    @ 2016-08-16 20:33:15
    #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
    @ 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
    @ 2014-06-08 19:07:00

    为什么在ZOJ、poj上过不去。。。在vijos上AC?

  • 0
    @ 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
    @ 2013-08-27 03:35:35

    思路就是先预处理方框的位置和大小然后暴搜出解

  • 0
    @ 2013-04-26 23:36:58

    = =i和j打错都能有75分

  • 0
    @ 2013-03-07 15:35:50

    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
    @ 2010-07-09 10:37:49

    其实这题可以不用搜索,要图论算法AC

    只要将题目转化为图,在进行拓补排序就是结果了

  • 0
    @ 2009-11-08 18:05:47

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    犯了低级错误 没想到还有75分

    题目不错

    纪念 200题

    • @ 2013-04-29 20:20:11

      0ms是什么情况?

  • 0
    @ 2009-11-05 08:07:34

    先找出有几个方框;

    分别分析每一个方框;

    {

    取出一种字母,就是一个方框;

    补齐残缺部分;

    补齐之后在原图中的坐标标记;

    }

    对每一个坐标,若标记的方框数量等于两个,则实际的方框在另一个之上;

    若标记的方框数量大于两个,则实际的方框在所有的之上;

    用一个有向图记录以上所得信息;

    g=1表示i不在j之上,即已知j在i之上;

    深度优先搜索得出所有解,约束条件g[a[i],a]=1;

    Q:如何补齐残缺部分?

    A:题目说‘每个方框的4条边都有一部分可见 一个角代表两条边’,由此可以知道补齐残缺部分的办法——从四边由边及里找到第一个出现的字母,即可确定方框的四边;

    P.S 这是我编程之前的思考,不知道有没有问题;

  • 0
    @ 2009-10-29 23:06:55

    Yeah!算是自己编过的。

    计算每个矩形边界,我的方法是读入时记录每行每列是否存在字符ch,然后逐行逐列扫描,得到mini,maxi,minj,maxj,就得到一个矩形的边界了。

    然后统计拓扑关系,DFS构造拓扑序列,快排后输出。

  • 0
    @ 2009-10-23 10:34:19

    拓扑排序?貌似我没用到。

    搜索排列树也没用。。

    方法与URAL 1006类似

    DFS每个字母,

    枚举长方形两顶点坐标

    若边上不是'*'或者当前字母就跳出。

    满足条件就把长方形的边全部改成‘*’号,继续DFS

    搜完之后给答案排序

    程序我就不帖了,5层循环太长太烦琐

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-10-08 18:57:58

    拓扑排序,就是有点烦,我第一次把i,j打错了,第二次就AC了

  • 0
    @ 2009-10-07 17:43:52

    好题。

  • 0
    @ 2009-09-18 20:56:56

    囧,交了4次

    把输入文件加上……

    我是傻子

  • 0
    @ 2009-09-01 20:08:00

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-08-29 11:55:41

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    此题乃好题。

信息

ID
1030
难度
5
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
1070
已通过
377
通过率
35%
上传者