提出 #219551


ソースコード 拡げる

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);
    if(N==1){
        answer[0][0] = '.';
    }
    REP(i,N)cout << answer[i] << endl;

    return 0;
}

提出情報

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

ジャッジ結果

セット名 得点 / 配点 テストケース
small 25 / 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 30 / 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 25 / 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 55 ms 16408 KB
0randomMasu2001.txt 54 ms 16416 KB
0randomMasu2002.txt 54 ms 16420 KB
0randomMasu2003.txt 54 ms 16540 KB
0randomMasu2004.txt 54 ms 16424 KB
0randomMasu3001.txt 54 ms 16416 KB
0randomMasu3002.txt 54 ms 16416 KB
0randomMasu3003.txt 54 ms 16412 KB
0randomMasu3004.txt 54 ms 16424 KB
0randomMasu3005.txt 54 ms 16416 KB
0randomMasu3006.txt 54 ms 16416 KB
0randomMasu3008.txt 54 ms 16416 KB
0randomMasu3010.txt 54 ms 16412 KB
0randomMasu3011.txt 52 ms 16416 KB
0randomMasu3012.txt 53 ms 16412 KB
0randomMasu3013.txt 53 ms 16416 KB
0randomMasu3014.txt 53 ms 16424 KB
0randomMasu3015.txt 52 ms 16416 KB
0randomMasu3016.txt 54 ms 16420 KB
0randomMasu3017.txt 54 ms 16420 KB
0randomMasu3018.txt 54 ms 16424 KB
0randomMasu3019.txt 52 ms 16420 KB
0sample1.txt 52 ms 16420 KB
1_manual1.txt 51 ms 16420 KB
1_manual2.txt 53 ms 16412 KB
1_manual3.txt 52 ms 16416 KB
1randomMasu004.txt 52 ms 16424 KB
1randomMasu005.txt 52 ms 16416 KB
1randomMasu006.txt 52 ms 16424 KB
1randomMasu007.txt 51 ms 16420 KB
1randomMasu008.txt 52 ms 16420 KB
1randomMasu009.txt 54 ms 16420 KB
1randomMasu4001.txt 53 ms 16416 KB
1randomMasu4002.txt 52 ms 16416 KB
1randomMasu4003.txt 52 ms 16420 KB
1randomMasu4004.txt 53 ms 16416 KB
1randomMasu4005.txt 54 ms 16416 KB
1randomMasu5001.txt 54 ms 16420 KB
1randomMasu5002.txt 54 ms 16408 KB
1randomMasu5003.txt 53 ms 16412 KB
1randomMasu5004.txt 53 ms 16416 KB
1randomMasu5005.txt 54 ms 16532 KB
1randomMasu6001.txt 54 ms 16412 KB
1randomMasu6002.txt 55 ms 16416 KB
1randomMasu6003.txt 53 ms 16420 KB
1randomMasu6004.txt 51 ms 16412 KB
1randomMasu6005.txt 51 ms 16416 KB
1randomMasu6006.txt 52 ms 16412 KB
1randomMasu7001.txt 51 ms 16420 KB
1randomMasu7002.txt 52 ms 16416 KB
1randomMasu7003.txt 52 ms 16412 KB
1randomMasu7004.txt 52 ms 16416 KB
1randomMasu7005.txt 52 ms 16424 KB
1randomMasu7006.txt 53 ms 16416 KB
1randomMasu7007.txt 52 ms 16416 KB
1randomMasu8001.txt 53 ms 16416 KB
1randomMasu8002.txt 52 ms 16416 KB
1randomMasu8003.txt 52 ms 16416 KB
1randomMasu8004.txt 54 ms 16416 KB
1randomMasu8005.txt 53 ms 16416 KB
1randomMasu8006.txt 54 ms 16404 KB
1randomMasu8007.txt 54 ms 16416 KB
1randomMasu8008.txt 53 ms 16416 KB
1randomMasu9001.txt 52 ms 16416 KB
1randomMasu9002.txt 53 ms 16424 KB
1randomMasu9003.txt 52 ms 16416 KB
1randomMasu9004.txt 51 ms 16416 KB
1randomMasu9005.txt 53 ms 16424 KB
1randomMasu9006.txt 51 ms 16428 KB
1randomMasu9007.txt 52 ms 16416 KB
1randomMasu9008.txt 52 ms 16420 KB
1sample2.txt 56 ms 16420 KB
2_manual1.txt 305 ms 106132 KB
2_manual10.txt 53 ms 16420 KB
2_manual2.txt 313 ms 106140 KB
2_manual3.txt 457 ms 106140 KB
2_manual4.txt 476 ms 106148 KB
2_manual5.txt 86 ms 26404 KB
2_manual6.txt 98 ms 26400 KB
2_manual7.txt 98 ms 26404 KB
2_manual8.txt 56 ms 16420 KB
2_manual9.txt 53 ms 16416 KB
2randomMasu010.txt 54 ms 16408 KB
2randomMasu011.txt 53 ms 16412 KB
2randomMasu012.txt 54 ms 16412 KB
2randomMasu013.txt 53 ms 16420 KB
2randomMasu014.txt 54 ms 16420 KB
2randomMasu015.txt 57 ms 16356 KB
2randomMasu016.txt 55 ms 16416 KB
2randomMasu017.txt 54 ms 16416 KB
2randomMasu018.txt 54 ms 16412 KB
2randomMasu019.txt 54 ms 16420 KB
2randomMasu100.txt 62 ms 17956 KB
2randomMasu101.txt 62 ms 17956 KB
2randomMasu102.txt 61 ms 18076 KB
2randomMasu103.txt 61 ms 18080 KB
2randomMasu104.txt 60 ms 18076 KB
2randomMasu105.txt 60 ms 18084 KB
2randomMasu106.txt 60 ms 18216 KB
2randomMasu107.txt 62 ms 18208 KB
2randomMasu108.txt 62 ms 18200 KB
2randomMasu109.txt 63 ms 18212 KB
2randomMasu300.txt 119 ms 30752 KB
2randomMasu301.txt 121 ms 30880 KB
2randomMasu302.txt 121 ms 30948 KB
2randomMasu303.txt 122 ms 31000 KB
2randomMasu304.txt 122 ms 31128 KB
2randomMasu305.txt 122 ms 31268 KB
2randomMasu306.txt 121 ms 31392 KB
2randomMasu307.txt 120 ms 31520 KB
2randomMasu308.txt 124 ms 31520 KB
2randomMasu309.txt 122 ms 31652 KB
2randomMasu500.txt 235 ms 56228 KB
2randomMasu501.txt 237 ms 56360 KB
2randomMasu502.txt 237 ms 56480 KB
2randomMasu503.txt 238 ms 56740 KB
2randomMasu504.txt 242 ms 56868 KB
2randomMasu505.txt 242 ms 57056 KB
2randomMasu506.txt 242 ms 57124 KB
2randomMasu507.txt 242 ms 57372 KB
2randomMasu508.txt 244 ms 57496 KB
2randomMasu509.txt 248 ms 57632 KB
2randomMasu740.txt 458 ms 103836 KB
2randomMasu741.txt 459 ms 104092 KB
2randomMasu742.txt 461 ms 104220 KB
2randomMasu743.txt 457 ms 104480 KB
2randomMasu744.txt 486 ms 104740 KB
2randomMasu745.txt 489 ms 105000 KB
2randomMasu746.txt 470 ms 105248 KB
2randomMasu747.txt 468 ms 105508 KB
2randomMasu748.txt 475 ms 105628 KB
2randomMasu749.txt 498 ms 105944 KB
2randomMasu750.txt 472 ms 106140 KB
2randomMasu750b.txt 394 ms 106140 KB
2sample3.txt 56 ms 16412 KB