當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

洛谷P3585 [POI2015]PIE

發布時間：2023/12/18 编程问答 23 如意码农

生活随笔收集整理的這篇文章主要介紹了洛谷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 ;

}

總結

以上是生活随笔為你收集整理的洛谷P3585 [POI2015]PIE的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

洛谷
Pie