洛谷P3585 [POI2015]PIE

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

传送门

题目大意： 有个n*m的格子图，要求'x'点要被染成黑色

有个a*b的印章，'x'是可以染色的印章上的点。

要求用印章去染色格子

（1）印章不可以旋转。

（2）不能把墨水印到纸外面。

（3）纸上的同一个格子不可以印多次。

题解：模拟

从题目中可以看出，一定要让印章的左上角对应目前n*m方

格中未染色的左上角。因为要求不能重复染色，可以每染完

一个格子就把它赋值为0.（待染色为1）。

开始纯模拟，没有任何优化的代码。

加了个读入优化还是T了两个点，3000ms+

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 1022

using namespace std;

int n,m,a,b,fa,fb,cnt,q;

int map[N][N],yz[N][N];

char s[N];

inline int read(int &x){

    char ch=getchar();x=;int f=;

    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';

    x=x*f;

}

void init(){

    memset(map,,sizeof(map));

    memset(yz,,sizeof(yz));

    cnt=;fa=;fb=;

}

bool check(int x,int y){

    int xx=x-fa,yy=y-fb;

    for(int i=;i<=a;i++){

        for(int j=;j<=b;j++){

            if(yz[i][j]==)continue;

            int rx=xx+i,ry=yy+j;

            if(rx<||ry<||rx>n||ry>m||map[rx][ry]==)return false;

            map[rx][ry]=;cnt--;

        }

    }

    return true;

}

int main(){

    scanf("%d",&q);

    while(q--){

        init();bool flag=false;

       // scanf("%d%d%d%d",&n,&m,&a,&b);

      //  n=read();m=read();a=read();b=read();

       read(n);read(m);read(a);read(b);

        for(int i=;i<=n;i++){

            scanf("%s",s+);

            for(int j=;j<=m;j++)

             if(s[j]=='x')map[i][j]=,cnt++;

        }

        for(int i=;i<=a;i++){

            scanf("%s",s+);

            for(int j=;j<=b;j++){

                if(s[j]=='.')continue;

                if(!fa&&!fb)fa=i,fb=j;

                yz[i][j]=;

            }

        }

        for(register int i=;i<=n;i++){

            for(int j=;j<=m;j++){

                if(map[i][j]){

                    if(check(i,j)==){

                        printf("NIE\n");

                        flag=true;break;

                    }

                    if(cnt==){

                        printf("TAK\n");

                        flag=true;break;

                    }

                }

            }

            if(flag)break;

        }

    }

    return ;

}

看了题解... 想到以前做靶型数独这个题，把未填数的格子放到一个结构体里。

w[i].x,w[i].y分别表示第i个没有填数格子的横纵坐标。

这样的好处是不用遍历整张图，就找到了没填数的格子。

这个题也是这样....

上面的代码不仅遍历了一遍要染色的图，还遍历了整个印章。

最差的情况是10^12...遍历要染色的10^6,印章10^6。

所以把要染色的点和能染色的点抽离出来，放到结构体里。

很好的一个优化，188ms。

ps:某一行后面+***，可以这样理解..

yz[1].x+xx=x,yz[1].y+yy=y.

说明印章的左上角的可以染色的点，要对应

n*m的棋盘要加xx和yy，那么其他可以染色的点也要加这两个数

来对应他们要染色的点。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 1009

using namespace std;

int n,m,a,b,cnt_black,yz_black,q;

char s[N];

int map[N][N];

struct Make_Black{

    int x,y;

}gz[N*N],yz[N*N];

bool check(int x,int y){

    int xx=x-yz[].x,yy=y-yz[].y;  //***

    for(int i=;i<=yz_black;i++){

        int nx=yz[i].x+xx,ny=yz[i].y+yy;

        if(nx<||nx>n||ny<||ny>m||map[nx][ny]==)return false;

        map[nx][ny]=false;

    }

    return true;

}

int main(){

    scanf("%d",&q);

    while(q--){

        bool flag=false;

        cnt_black=yz_black=;

        scanf("%d%d%d%d",&n,&m,&a,&b);

        memset(map,,sizeof(map));

        for(int i=;i<=n;i++){

            scanf("%s",s+);

            for(int j=;j<=m;j++)

             if(s[j]=='x'){

                 gz[++cnt_black].x=i;gz[cnt_black].y=j;

                 map[i][j]=true;

             }

        }

        for(int i=;i<=a;i++){

            scanf("%s",s+);

            for(int j=;j<=b;j++)

             if(s[j]=='x')yz[++yz_black].x=i,yz[yz_black].y=j;

        }

        for(int i=;i<=cnt_black;i++){

            if(map[gz[i].x][gz[i].y])

             if(check(gz[i].x,gz[i].y)==){

                 flag=true;

                 printf("NIE\n");break;

             }

        }

        if(!flag)printf("TAK\n");

    }

    return ;

}