ECNA 2018 E The Punctilious Cruciverbalist

2019-07-10 by fffasttime·0评论

题目描述是一个填单词的游戏，要按给定的计分方法按顺序填，这个不难。不过标号要自己算出来，这个不注意容易弄错。总而言之就是个小模拟题。

```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
char s[100];
```
```
int fi[100][100];
```
```
 
```
```
struct Node{
```
```
    int dx, dy;
```
```
    int m,msum;
```
```
    int num;
```
```
    int r; //0 row or 1 col
```

    void c(){int g=__gcd(m,msum);m/=g;msum/=g;}

    bool operator<(const Node &v) const{

    if ((double)m/msum==(double)v.m/v.msum){

```
        if (r==v.r) return num<v.num;
```
```
        return r<v.r;
```
```
    }
```

    return (double)m/msum>(double)v.m/v.msum;

```
    }
```
```
    void prt(){
```

    printf("%d%c %d/%d (%d,%d)\n",num,r?'D':'A',m,msum,dx,dy);

```
    }
```
```
}clu[10000];
```
```
int n,m;
```
```
 
```
```
bool fill(){
```
```
    int cluc=0;
```
```
    int gcnt=1;
```
```
    for (int i=0;i<n;i++){
```

    for (int j=0;j<m;j++) if (fi[i][j]!=-1){

```
        bool gg=0;
```
```
        if (j==0 || fi[i][j-1]==-1){
```
```
        bool used=0; int k;
```
```
        gg=1;
```

        for (k=j;k<m && fi[i][k]!=-1;k++){

```
            if (fi[i][k]==0) used=1;
```
```
        }
```
```
        k--; int r=1,msum=0,m=0;
```
```
        if (!used) goto next;
```
```
        for (;k>=j;k--,r++){
```
```
            if (fi[i][k]==1) m+=r;
```
```
            msum+=r; 
```
```
        }
```

        clu[cluc++]=(Node){i,j,m,msum,gcnt,0};

```
        clu[cluc-1].c();
```
```
        }
```
```
next:
```
```
        if (i==0 || fi[i-1][j]==-1){
```
```
        bool used=0; int k;
```
```
        gg=1;
```

        for (k=i;k<n && fi[k][j]!=-1;k++){

```
            if (fi[k][j]==0) used=1;
```
```
        }
```
```
        k--; int r=1,msum=0,m=0;
```
```
        if (!used) goto next2;
```
```
        for (;k>=i;k--,r++){
```
```
            if (fi[k][j]==1) m+=r;
```
```
            msum+=r;
```
```
        }   
```

        clu[cluc++]=(Node){i,j,m,msum,gcnt,1};

```
        clu[cluc-1].c();
```
```
        }
```
```
next2:
```
```
        if (gg) gcnt++;
```
```
    }
```
```
    }
```
```
    if (cluc==0) return 0;
```
```
    sort(clu,clu+cluc);
```

    //for (int i=0;i<cluc;i++) clu[i].prt();

```
    if (clu[0].r==0){
```
```
    printf("%dA\n",clu[0].num);
```
```
    int i=clu[0].dx,k=clu[0].dy;
```
```
    for (;k<m && fi[i][k]!=-1;k++)
```
```
        fi[i][k]=1; 
```
```
    }
```
```
    else{
```
```
    printf("%dD\n",clu[0].num);
```
```
    int j=clu[0].dy,k=clu[0].dx;
```
```
    for (;k<n && fi[k][j]!=-1;k++){
```
```
        fi[k][j]=1;
```
```
    }
```
```
 
```
```
    }
```

    //for (int i=0;i<n;i++,cout<<'\n') for (int j=0;j<m;j++) cout<<fi[i][j]<<' ';

```
    //getchar(); getchar();
```
```
    return 1;
```
```
}
```
```
 
```
```
int main(){
```
```
    cin>>n>>m;
```
```
    for (int i=0;i<n;i++){
```
```
    cin>>s;
```
```
    for (int j=0;j<m;j++){
```
```
        if (s[j]=='.') fi[i][j]=0;
```

        else if (s[j]=='#') fi[i][j]=-1;

```
        else fi[i][j]=1;
```
```
    }
```
```
 
```
```
    }
```
```
    while (fill());
```
```
    return 0;
```
```
}
```

发表评论取消回复