結果

問題 No.460 裏表ちわーわ
コンテスト
ユーザー mai
提出日時 2016-12-11 02:17:33
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,770 bytes
コンパイル時間 2,196 ms
コンパイル使用メモリ 187,812 KB
実行使用メモリ 409,784 KB
最終ジャッジ日時 2024-11-29 02:58:20
合計ジャッジ時間 64,492 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 7 TLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;

#define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;
#define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;
#define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;}
#define ALL(v) (v).begin(),(v).end()
#define BIGINT 0x7FFFFFFF
#define E107 1000000007
void printbit(int u){if(u==0)cout<<0;else{int s=0,k=0;for(;0<u;u>>=1,k++)s=(s<<1)|(u&1);for(;0<k--;s>>=1)cout<<(s&1);}}

#define TIME chrono::system_clock::now()
#define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count())

template<typename T1,typename T2>
ostream& operator <<(ostream &o,const pair<T1,T2> p){o<<"("<<p.first<<":"<<p.second<<")";return o;}

int width,height;
int m,n;

struct Field{
    int height,width;
    vector<int> data;
    Field(int h,int w){
        height = h;
        width = w;
        data.resize(h*w);
    }
    
    int& operator()(int y,int x){
        return data[y*width+x];
    }
    
    bool operator<(const Field& f) const{
        return data < f.data;
    }
    bool operator==(const Field& f) const{
        return height==f.height && width == f.width && data == f.data;
    }
    
    void flipx(){
        int x,y;
        for (y=0;y<height;y++)
            for (x=0;x<width/2;x++){
                swap(operator()(y,x),operator()(y,width-x-1));
            }
    }
    void flipy(){
        int x,y;
        for (x=0;x<width;x++)
            for (y=0;y<height/2;y++){
                swap(operator()(y,x),operator()(height-y-1,x));
            }
    }
    
};

map<Field,int> dp;

void flipx(vector<vector<int>>& field){
    int x,y;
    for (y=0;y<height;y++)
        for (x=0;x<width/2;x++){
            swap(field[y][x],field[y][width-x-1]);
        }
    return;
}
void flipy(vector<vector<int>>& field){
    int x,y;
    for (y=0;y<height/2;y++){
        field[y].swap(field[height-y-1]);
    }
    return;
}

int main(){
    int i,j,k;
    int x,y,a,b;
    
    cin >> height >> width;
    
    Field first(height,width); // cww
    Field final(height,width); // zero
    
    for (y=0;y<height;y++){
        for (x=0;x<width;x++){
            cin >> first(y,x);
        }
    }
    
    // all zero
    
    queue<pair<int,Field> > q;
    
    //q.push(make_pair(1,final));
    q.push(make_pair(1,first));
    dp[final] = 1;
    //q.push(make_pair(10001,first));
    //dp[first] = 10001;
    
    auto tim = TIME;
    
    while (!q.empty()){
        if (MILLISEC(TIME-tim)>7000) break;
        auto p = q.front();
        q.pop();
        
        //if (dp.size()>100000){
        //    cout << dp.size() << endl;return 0;
        //}
        
        if (p.second == final){
            cout << (p.first-1) << endl;
            return 0;
        }
        // if (p.first<10000 && p.second == first){
        //     cout << (p.first-1) << endl;
        //     return 0;
        // }
        // if (p.first>=10000 && p.second == final){
        //     cout << (p.first-10001) << endl;
        //     return 0;
        // }
        
        for (y=0;y<height;y++){
            for (x=0;x<width;x++){
                if (p.second(y,x)==0) continue;
                Field tmp = p.second;
                for (i=-1+(x==0);i<=1-(x==width-1);i++){
                    for (j=-1+(y==0);j<=1-(y==height-1);j++){
                        tmp(y+j,x+i)^=1;
                    }
                }
                Field tmp2 = tmp;
                
                for (i=1;i<4;i++){
                    if (i%2==1){
                        tmp2.flipx();
                    }
                    if ((i/2)%2==1){
                        tmp2.flipy();
                    }
                    
                    if (tmp2 < tmp) tmp = tmp2;
                }
                
                int &val = dp[tmp];
                if (val!=0){
                    if ((p.first<=10000)^(val<=10000)){
                        //printf("%d %d\n",p.first,val);
                        //cout << "!";
                        cout << (p.first+val-10001) << endl;
                        return 0;
                    }
                }else{
                    //val = p.first+1;
                    val = p.first+1;
                    q.push(make_pair(p.first+1,tmp));
                }
                
            }
        }
        
        
    }
    
    //cout << dp.size() << endl;
    
    cout << "Impossible" << endl;

    return 0;
}
0