提出 #219524


ソースコード 拡げる

Copy
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

#define REP(i,x) for(int i=0 ; i<(int)(x) ; i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int N;
vector<string> field;
vector<string> answer;

int memo[1000][1000][2][2];

const int dy[4] = {0,1,0,-1};
const int dx[4] = {1,0,-1,0};

bool valid(int x, int y){
    return x>=0 && x<N && y>=0 && y<N;
}

bool rec(int x,int y){
    if(y==N)return true;


    int a = 0, b = 0;
    if(x>0)a = answer[y][x-1]=='#' ? 1 : 0;
    if(y>0)b = answer[y-1][x]=='#' ? 1 : 0;
    if(memo[y][x][a][b] == -1)return false;

    if(x==N)return rec(0, y+1);


    for(int b=0 ; b<(1<<4) ; b++){
        char draw[4];
        int cnt = 0;
        REP(i,4){
            draw[i] = (b>>i&1) ? '#' : '.';
            int ny = y+dy[i];
            int nx = x+dx[i];
            if(valid(nx,ny)){
                cnt += (b>>i&1);
            }
        }

        if(field[y][x]=='.' && cnt%2==1)continue;
        if(field[y][x]=='#' && cnt%2==0)continue;

        bool ok = true;
        REP(i,4){
            int ny = y+dy[i];
            int nx = x+dx[i];
            if(valid(nx,ny)){
                if(answer[ny][nx]==' ')continue;
                if(answer[ny][nx]!=draw[i])ok = false;
            }
        }
        if(ok){
            bool changed[4];
            memset(changed, false, sizeof(changed));
            REP(i,4){
                int ny = y+dy[i];
                int nx = x+dx[i];
                if(valid(nx,ny)){
                    if(answer[ny][nx]==' '){
                        answer[ny][nx] = draw[i];
                        changed[i] = true;
                    }
                }
            }
            if(rec(x+1,y)==1)return true;
            REP(i,4){
                int ny = y+dy[i];
                int nx = x+dx[i];
                if(valid(nx,ny) && changed[i]){
                    answer[ny][nx]=' ';
                }
            }
        }
    }
    memo[y][x][a][b] = -1;
    return false;


}


int main(){
    cin >> N;
    field.resize(N);
    answer.resize(N);
    REP(i,N)cin >> field[i];
    REP(i,N)answer[i] = string(N,' ');

    memset(memo, 0, sizeof(memo));
    rec(0,0);
    REP(i,N)cout << answer[i] << endl;

    return 0;
}

提出情報

提出日時
問題 C - 天下一王国の歴史
ユーザ nel215
言語 C++ (G++ 4.6.4)
得点 0
コード長 2606 Byte
結果
実行時間 476 ms
メモリ 106412 KB

ジャッジ結果

セット名 得点 / 配点 テストケース
small 0 / 25 0randomMasu1001.txt, 0randomMasu2001.txt, 0randomMasu2002.txt, 0randomMasu2003.txt, 0randomMasu2004.txt, 0randomMasu3001.txt, 0randomMasu3002.txt, 0randomMasu3003.txt, 0randomMasu3004.txt, 0randomMasu3005.txt, 0randomMasu3006.txt, 0randomMasu3008.txt, 0randomMasu3010.txt, 0randomMasu3011.txt, 0randomMasu3012.txt, 0randomMasu3013.txt, 0randomMasu3014.txt, 0randomMasu3015.txt, 0randomMasu3016.txt, 0randomMasu3017.txt, 0randomMasu3018.txt, 0randomMasu3019.txt, 0sample1.txt
medium 0 / 30 0randomMasu1001.txt, 0randomMasu2001.txt, 0randomMasu2002.txt, 0randomMasu2003.txt, 0randomMasu2004.txt, 0randomMasu3001.txt, 0randomMasu3002.txt, 0randomMasu3003.txt, 0randomMasu3004.txt, 0randomMasu3005.txt, 0randomMasu3006.txt, 0randomMasu3008.txt, 0randomMasu3010.txt, 0randomMasu3011.txt, 0randomMasu3012.txt, 0randomMasu3013.txt, 0randomMasu3014.txt, 0randomMasu3015.txt, 0randomMasu3016.txt, 0randomMasu3017.txt, 0randomMasu3018.txt, 0randomMasu3019.txt, 0sample1.txt, 1_manual1.txt, 1_manual2.txt, 1_manual3.txt, 1randomMasu004.txt, 1randomMasu005.txt, 1randomMasu006.txt, 1randomMasu007.txt, 1randomMasu008.txt, 1randomMasu009.txt, 1randomMasu4001.txt, 1randomMasu4002.txt, 1randomMasu4003.txt, 1randomMasu4004.txt, 1randomMasu4005.txt, 1randomMasu5001.txt, 1randomMasu5002.txt, 1randomMasu5003.txt, 1randomMasu5004.txt, 1randomMasu5005.txt, 1randomMasu6001.txt, 1randomMasu6002.txt, 1randomMasu6003.txt, 1randomMasu6004.txt, 1randomMasu6005.txt, 1randomMasu6006.txt, 1randomMasu7001.txt, 1randomMasu7002.txt, 1randomMasu7003.txt, 1randomMasu7004.txt, 1randomMasu7005.txt, 1randomMasu7006.txt, 1randomMasu7007.txt, 1randomMasu8001.txt, 1randomMasu8002.txt, 1randomMasu8003.txt, 1randomMasu8004.txt, 1randomMasu8005.txt, 1randomMasu8006.txt, 1randomMasu8007.txt, 1randomMasu8008.txt, 1randomMasu9001.txt, 1randomMasu9002.txt, 1randomMasu9003.txt, 1randomMasu9004.txt, 1randomMasu9005.txt, 1randomMasu9006.txt, 1randomMasu9007.txt, 1randomMasu9008.txt, 1sample2.txt
All 0 / 25 0randomMasu1001.txt, 0randomMasu2001.txt, 0randomMasu2002.txt, 0randomMasu2003.txt, 0randomMasu2004.txt, 0randomMasu3001.txt, 0randomMasu3002.txt, 0randomMasu3003.txt, 0randomMasu3004.txt, 0randomMasu3005.txt, 0randomMasu3006.txt, 0randomMasu3008.txt, 0randomMasu3010.txt, 0randomMasu3011.txt, 0randomMasu3012.txt, 0randomMasu3013.txt, 0randomMasu3014.txt, 0randomMasu3015.txt, 0randomMasu3016.txt, 0randomMasu3017.txt, 0randomMasu3018.txt, 0randomMasu3019.txt, 0sample1.txt, 1_manual1.txt, 1_manual2.txt, 1_manual3.txt, 1randomMasu004.txt, 1randomMasu005.txt, 1randomMasu006.txt, 1randomMasu007.txt, 1randomMasu008.txt, 1randomMasu009.txt, 1randomMasu4001.txt, 1randomMasu4002.txt, 1randomMasu4003.txt, 1randomMasu4004.txt, 1randomMasu4005.txt, 1randomMasu5001.txt, 1randomMasu5002.txt, 1randomMasu5003.txt, 1randomMasu5004.txt, 1randomMasu5005.txt, 1randomMasu6001.txt, 1randomMasu6002.txt, 1randomMasu6003.txt, 1randomMasu6004.txt, 1randomMasu6005.txt, 1randomMasu6006.txt, 1randomMasu7001.txt, 1randomMasu7002.txt, 1randomMasu7003.txt, 1randomMasu7004.txt, 1randomMasu7005.txt, 1randomMasu7006.txt, 1randomMasu7007.txt, 1randomMasu8001.txt, 1randomMasu8002.txt, 1randomMasu8003.txt, 1randomMasu8004.txt, 1randomMasu8005.txt, 1randomMasu8006.txt, 1randomMasu8007.txt, 1randomMasu8008.txt, 1randomMasu9001.txt, 1randomMasu9002.txt, 1randomMasu9003.txt, 1randomMasu9004.txt, 1randomMasu9005.txt, 1randomMasu9006.txt, 1randomMasu9007.txt, 1randomMasu9008.txt, 1sample2.txt, 2_manual1.txt, 2_manual10.txt, 2_manual2.txt, 2_manual3.txt, 2_manual4.txt, 2_manual5.txt, 2_manual6.txt, 2_manual7.txt, 2_manual8.txt, 2_manual9.txt, 2randomMasu010.txt, 2randomMasu011.txt, 2randomMasu012.txt, 2randomMasu013.txt, 2randomMasu014.txt, 2randomMasu015.txt, 2randomMasu016.txt, 2randomMasu017.txt, 2randomMasu018.txt, 2randomMasu019.txt, 2randomMasu100.txt, 2randomMasu101.txt, 2randomMasu102.txt, 2randomMasu103.txt, 2randomMasu104.txt, 2randomMasu105.txt, 2randomMasu106.txt, 2randomMasu107.txt, 2randomMasu108.txt, 2randomMasu109.txt, 2randomMasu300.txt, 2randomMasu301.txt, 2randomMasu302.txt, 2randomMasu303.txt, 2randomMasu304.txt, 2randomMasu305.txt, 2randomMasu306.txt, 2randomMasu307.txt, 2randomMasu308.txt, 2randomMasu309.txt, 2randomMasu500.txt, 2randomMasu501.txt, 2randomMasu502.txt, 2randomMasu503.txt, 2randomMasu504.txt, 2randomMasu505.txt, 2randomMasu506.txt, 2randomMasu507.txt, 2randomMasu508.txt, 2randomMasu509.txt, 2randomMasu740.txt, 2randomMasu741.txt, 2randomMasu742.txt, 2randomMasu743.txt, 2randomMasu744.txt, 2randomMasu745.txt, 2randomMasu746.txt, 2randomMasu747.txt, 2randomMasu748.txt, 2randomMasu749.txt, 2randomMasu750.txt, 2randomMasu750b.txt, 2sample3.txt
ケース名 結果 実行時間 メモリ
0randomMasu1001.txt 61 ms 16548 KB
0randomMasu2001.txt 56 ms 16548 KB
0randomMasu2002.txt 57 ms 16608 KB
0randomMasu2003.txt 53 ms 16468 KB
0randomMasu2004.txt 58 ms 16552 KB
0randomMasu3001.txt 63 ms 16464 KB
0randomMasu3002.txt 59 ms 16552 KB
0randomMasu3003.txt 57 ms 16460 KB
0randomMasu3004.txt 57 ms 16468 KB
0randomMasu3005.txt 55 ms 16624 KB
0randomMasu3006.txt 59 ms 16472 KB
0randomMasu3008.txt 57 ms 16548 KB
0randomMasu3010.txt 59 ms 16548 KB
0randomMasu3011.txt 59 ms 16552 KB
0randomMasu3012.txt 58 ms 16548 KB
0randomMasu3013.txt 53 ms 16612 KB
0randomMasu3014.txt 61 ms 16480 KB
0randomMasu3015.txt 54 ms 16548 KB
0randomMasu3016.txt 59 ms 16548 KB
0randomMasu3017.txt 54 ms 16552 KB
0randomMasu3018.txt 57 ms 16624 KB
0randomMasu3019.txt 64 ms 16464 KB
0sample1.txt 62 ms 16548 KB
1_manual1.txt 59 ms 16472 KB
1_manual2.txt 54 ms 16472 KB
1_manual3.txt 52 ms 16544 KB
1randomMasu004.txt 55 ms 16548 KB
1randomMasu005.txt 55 ms 16492 KB
1randomMasu006.txt 52 ms 16484 KB
1randomMasu007.txt 61 ms 16492 KB
1randomMasu008.txt 60 ms 16548 KB
1randomMasu009.txt 53 ms 16616 KB
1randomMasu4001.txt 58 ms 16548 KB
1randomMasu4002.txt 61 ms 16560 KB
1randomMasu4003.txt 54 ms 16468 KB
1randomMasu4004.txt 59 ms 16468 KB
1randomMasu4005.txt 57 ms 16552 KB
1randomMasu5001.txt 58 ms 16548 KB
1randomMasu5002.txt 60 ms 16572 KB
1randomMasu5003.txt 60 ms 16548 KB
1randomMasu5004.txt 58 ms 16492 KB
1randomMasu5005.txt 59 ms 16548 KB
1randomMasu6001.txt 60 ms 16544 KB
1randomMasu6002.txt 61 ms 16448 KB
1randomMasu6003.txt 54 ms 16472 KB
1randomMasu6004.txt 51 ms 16472 KB
1randomMasu6005.txt 53 ms 16556 KB
1randomMasu6006.txt 54 ms 16612 KB
1randomMasu7001.txt 59 ms 16488 KB
1randomMasu7002.txt 55 ms 16472 KB
1randomMasu7003.txt 53 ms 16544 KB
1randomMasu7004.txt 59 ms 16556 KB
1randomMasu7005.txt 54 ms 16552 KB
1randomMasu7006.txt 59 ms 16548 KB
1randomMasu7007.txt 59 ms 16548 KB
1randomMasu8001.txt 60 ms 16544 KB
1randomMasu8002.txt 53 ms 16544 KB
1randomMasu8003.txt 60 ms 16480 KB
1randomMasu8004.txt 54 ms 16544 KB
1randomMasu8005.txt 60 ms 16544 KB
1randomMasu8006.txt 59 ms 16544 KB
1randomMasu8007.txt 55 ms 16612 KB
1randomMasu8008.txt 59 ms 16468 KB
1randomMasu9001.txt 58 ms 16552 KB
1randomMasu9002.txt 58 ms 16616 KB
1randomMasu9003.txt 57 ms 16556 KB
1randomMasu9004.txt 53 ms 16544 KB
1randomMasu9005.txt 58 ms 16552 KB
1randomMasu9006.txt 60 ms 16544 KB
1randomMasu9007.txt 61 ms 16612 KB
1randomMasu9008.txt 59 ms 16472 KB
1sample2.txt 60 ms 16496 KB
2_manual1.txt 320 ms 106268 KB
2_manual10.txt 58 ms 16548 KB
2_manual2.txt 308 ms 106412 KB
2_manual3.txt 463 ms 106328 KB
2_manual4.txt 456 ms 106272 KB
2_manual5.txt 90 ms 26536 KB
2_manual6.txt 109 ms 26536 KB
2_manual7.txt 100 ms 26536 KB
2_manual8.txt 61 ms 16592 KB
2_manual9.txt 55 ms 16620 KB
2randomMasu010.txt 52 ms 16612 KB
2randomMasu011.txt 55 ms 16544 KB
2randomMasu012.txt 59 ms 16544 KB
2randomMasu013.txt 53 ms 16552 KB
2randomMasu014.txt 53 ms 16548 KB
2randomMasu015.txt 55 ms 16496 KB
2randomMasu016.txt 58 ms 16620 KB
2randomMasu017.txt 54 ms 16552 KB
2randomMasu018.txt 57 ms 16552 KB
2randomMasu019.txt 60 ms 16600 KB
2randomMasu100.txt 67 ms 18128 KB
2randomMasu101.txt 66 ms 18088 KB
2randomMasu102.txt 69 ms 18172 KB
2randomMasu103.txt 64 ms 18212 KB
2randomMasu104.txt 66 ms 18348 KB
2randomMasu105.txt 68 ms 18364 KB
2randomMasu106.txt 69 ms 18264 KB
2randomMasu107.txt 63 ms 18344 KB
2randomMasu108.txt 62 ms 18476 KB
2randomMasu109.txt 69 ms 18464 KB
2randomMasu300.txt 121 ms 30884 KB
2randomMasu301.txt 131 ms 31072 KB
2randomMasu302.txt 121 ms 31140 KB
2randomMasu303.txt 131 ms 31264 KB
2randomMasu304.txt 124 ms 31340 KB
2randomMasu305.txt 123 ms 31396 KB
2randomMasu306.txt 131 ms 31528 KB
2randomMasu307.txt 131 ms 31708 KB
2randomMasu308.txt 131 ms 31656 KB
2randomMasu309.txt 130 ms 31780 KB
2randomMasu500.txt 233 ms 56408 KB
2randomMasu501.txt 253 ms 56476 KB
2randomMasu502.txt 240 ms 56740 KB
2randomMasu503.txt 253 ms 56864 KB
2randomMasu504.txt 251 ms 56996 KB
2randomMasu505.txt 240 ms 57128 KB
2randomMasu506.txt 248 ms 57376 KB
2randomMasu507.txt 259 ms 57512 KB
2randomMasu508.txt 257 ms 57632 KB
2randomMasu509.txt 254 ms 57768 KB
2randomMasu740.txt 465 ms 103908 KB
2randomMasu741.txt 457 ms 104220 KB
2randomMasu742.txt 454 ms 104480 KB
2randomMasu743.txt 458 ms 104612 KB
2randomMasu744.txt 463 ms 104868 KB
2randomMasu745.txt 476 ms 105080 KB
2randomMasu746.txt 452 ms 105384 KB
2randomMasu747.txt 458 ms 105596 KB
2randomMasu748.txt 474 ms 105896 KB
2randomMasu749.txt 463 ms 106084 KB
2randomMasu750.txt 474 ms 106280 KB
2randomMasu750b.txt 390 ms 106276 KB
2sample3.txt 58 ms 16548 KB