#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
256 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1080 ms |
256 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
