oj.uz

답안 #99755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
99755 2019-03-06T19:44:44 Z fabjanm Trapezi (COI17_trapezi) C++
0 / 100
 500 ms 256 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>

using namespace std;

int n;

char mat[10][20];

int a[10][20];
int boje_prav[10][20];
int obojan[10][20];

void input(){
    cin>>n;

    memset(mat,'-',sizeof(mat));
    char ch;
    int st=n-1,br=2*n+1;
    for(int i=0;i<n;i++){
        int st1=st;
        for(int j=0;j<br;j++){
            cin>>ch;
            mat[i][st1]=ch;
            st1++;
        }
        st--;
        br+=2;
    }

    br-=2,st++;
    for(int i=n;i<n*2;i++){
        int st1=st;
        for(int j=0;j<br;j++){
            cin>>ch;
            mat[i][st1]=ch;
            st1++;
        }
        st++;
        br-=2;
    }

    /*cout<<endl;
    for(int i=0;i<n*2;i++){
        for(int j=0;j<(n*2+1)+(n-1)*2;j++){
            cout<<mat[i][j];
        }
        cout<<endl;
    }
    cout<<endl;*/
}

bool prov(){
    for(int i=0;i<n*2;i++){
        for(int j=0;j<(n*2+1)+(n-1)*2;j++){
            if(mat[i][j]=='0' && a[i][j]==0)return false;
        }
    }
    return true;
}

bool ok(int a, int b, int c, int x){
    return a==x && b==x && c==x;
}

bool rek(int r, int s){
    //system("pause");
    ///cout<<r<<" "<<s<<endl;
    if(r>=n*2-1 && s>=n*2){
        if(prov()){
            //cout<<111111111;
            return true;
        }
        else return false;
    }

    if(s>=(n*2+1)+(n-1)*2)rek(r+1,0);
    if(mat[r][s]=='-' || mat[r][s]=='.')rek(r, s+1);
    if(a[r][s]!=0)rek(r,s+1);

    ///cout<<" --->  "<<r<<" "<<s<<endl;

    if(s+1<(n*2+1)+(n-1)*2 && r+1<n*2 && ok(a[r][s],a[r+1][s],a[r][s+1],0) && boje_prav[r][s]==1 && ok(mat[r][s],mat[r+1][s],mat[r][s+1],'0')){
        //cout<<r<<" "<<s<<endl;
        ///cout<<r<<" "<<s<<"  "<<"usao sam u ovaj oblik: 1"<<endl;
        a[r][s]=a[r+1][s]=a[r][s+1]=1;
        rek(r,s+1);
        a[r][s]=a[r+1][s]=a[r][s+1]=0;
    }
    if(s+1<(n*2+1)+(n-1)*2 && r+1<n*2 && ok(a[r][s],a[r][s+1],a[r+1][s+1],0) && boje_prav[r][s]==2 && ok(mat[r][s],mat[r][s+1],mat[r+1][s+1],'0')){
        //cout<<r<<"  "<<s<<endl;
        ///cout<<r<<" "<<s<<"  "<<"usao sam u ovaj oblik: 2"<<endl;
        a[r][s]=a[r][s+1]=a[r+1][s+1]=2;
        rek(r,s+1);
        a[r][s]=a[r][s+1]=a[r+1][s+1]=0;
    }
    if(s-1>=0 && r+1<n*2 && ok(a[r][s],a[r+1][s],a[r+1][s-1],0) && boje_prav[r][s]==1 && ok(mat[r][s],mat[r+1][s],mat[r+1][s-1],'0')){
        //cout<<r<<" "<<s<<endl;
        ///cout<<r<<" "<<s<<"  "<<"usao sam u ovaj oblik: 3"<<endl;
        a[r][s]=a[r+1][s]=a[r+1][s-1]=3;
        rek(r,s+1);
        a[r][s]=a[r+1][s]=a[r+1][s-1]=0;
    }
    if(s+1<(n*2+1)+(n-1)*2 && r+1<n*2 && ok(a[r][s],a[r+1][s],a[r+1][s+1],0) && boje_prav[r][s]==1 && ok(mat[r][s],mat[r+1][s],mat[r+1][s+1],'0')){
        //cout<<r<<" "<<s<<endl;
        ///cout<<r<<" "<<s<<"  "<<"usao sam u ovaj oblik: 4"<<endl;
        a[r][s]=a[r+1][s]=a[r+1][s+1]=4;
        rek(r,s+1);
        a[r][s]=a[r+1][s]=a[r+1][s+1]=0;
    }
    if(s+2<(n*2+1)+(n-1)*2 && r+1<n*2 && ok(a[r][s],a[r][s+1],a[r][s+2],0) && ok(mat[r][s],mat[r][s+1],mat[r][s+2],'0')){
        //out<<r<<" "<<s<<endl;
        ///cout<<r<<" "<<s<<"  "<<"usao sam u ovaj oblik: 5"<<endl;
        a[r][s]=a[r][s+1]=a[r][s+2]=5;
        rek(r,s+1);
        a[r][s]=a[r][s+1]=a[r][s+2]=0;
    }

    ///cout<<" ------------->  "<<r<<" "<<s<<endl;
    return false;
}

void bojanje(){
    memset(obojan,-1,sizeof(obojan));
    for(int i=0;i<n*2;i++){
        for(int j=0;j<(n*2+1)+(n-1)*2;j++){

        }
    }
}

void solve(){
    int boj=1;
    if(n-1 % 2 != 0)boj=2;
    for(int i=0;i<n*2;i++){
        for(int j=0;j<(n*2+1)+(n-1)*2;j++){
            boje_prav[i][j]=boj;
            if(boj==1)boj=2;
            else boj=1;
        }
    }

    /*for(int i=0;i<n*2;i++){
        for(int j=0;j<(n*2+1)+(n-1)*2;j++){
            cout<<boje_prav[i][j];
        }
        cout<<endl;
    }
    cout<<endl;*/

    if(rek(0,0)){
        cout<<"DAAAAAAA";
    }
    else{
        cout<<"nemoguce";
    }
}

int main(){
    input();
    solve();



    return 0;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1076 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1080 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -