HDU 5547 (DFS暴力)

#include "cstring" #include "cstdio" #include "string.h" #include "cstdio" #include "iostream" using namespace std; char mmap[10][10]; int num_cnt[10]; int row_cnt[10][10]; int column_cnt[10][10]; int flag; typedef struct node { int m,n; }node; node list[25]; int myflag=0; void num_check(int m,int n) { if(m<=2&&n<=2) { if(mmap[1][1]!='*') num_cnt[mmap[1][1]-'0']++; if(mmap[1][2]!='*') num_cnt[mmap[1][2]-'0']++; if(mmap[2][1]!='*') num_cnt[mmap[2][1]-'0']++; if(mmap[2][2]!='*') num_cnt[mmap[2][2]-'0']++; } if(m>=3&&n<=2) { if(mmap[3][1]!='*') num_cnt[mmap[3][1]-'0']++; if(mmap[3][2]!='*') num_cnt[mmap[3][2]-'0']++; if(mmap[4][1]!='*') num_cnt[mmap[4][1]-'0']++; if(mmap[4][2]!='*') num_cnt[mmap[4][2]-'0']++; } if(m<=2&&n>=3) { if(mmap[1][3]!='*') num_cnt[mmap[1][3]-'0']++; if(mmap[1][4]!='*') num_cnt[mmap[1][4]-'0']++; if(mmap[2][3]!='*') num_cnt[mmap[2][3]-'0']++; if(mmap[2][4]!='*') num_cnt[mmap[2][4]-'0']++; } if(m>=3&&n>=3) { if(mmap[3][3]!='*') num_cnt[mmap[3][3]-'0']++; if(mmap[3][4]!='*') num_cnt[mmap[3][4]-'0']++; if(mmap[4][3]!='*') num_cnt[mmap[4][3]-'0']++; if(mmap[4][4]!='*') num_cnt[mmap[4][4]-'0']++; } } void dfs(int step) { if(step==flag) return; node now=list[step]; memset(num_cnt,0,sizeof(num_cnt)); num_check(now.m,now.n); if(row_cnt[now.m][1]==0&&num_cnt[1]==0&&column_cnt[now.n][1]==0) { mmap[now.m][now.n]='1'; if(step==flag-1) { myflag=1; return; } row_cnt[now.m][1]++; column_cnt[now.n][1]++; dfs(step+1); if(myflag==1) return; mmap[now.m][now.n]='*'; row_cnt[now.m][1]--; column_cnt[now.n][1]--; } if(row_cnt[now.m][2]==0&&num_cnt[2]==0&&column_cnt[now.n][2]==0) { mmap[now.m][now.n]='2'; if(step==flag-1) { myflag=1; return; } row_cnt[now.m][2]++; column_cnt[now.n][2]++; dfs(step+1); if(myflag==1) return; mmap[now.m][now.n]='*'; row_cnt[now.m][2]--; column_cnt[now.n][2]--; } if(row_cnt[now.m][3]==0&&num_cnt[3]==0&&column_cnt[now.n][3]==0) { mmap[now.m][now.n]='3'; if(step==flag-1) { myflag=1; return; } row_cnt[now.m][3]++; column_cnt[now.n][3]++; dfs(step+1); if(myflag==1) return; mmap[now.m][now.n]='*'; row_cnt[now.m][3]--; column_cnt[now.n][3]--; } if(row_cnt[now.m][4]==0&&num_cnt[4]==0&&column_cnt[now.n][4]==0) { mmap[now.m][now.n]='4'; if(step==flag-1) { myflag=1; return; } row_cnt[now.m][4]++; column_cnt[now.n][4]++; dfs(step+1); if(myflag==1) return; mmap[now.m][now.n]='*'; row_cnt[now.m][4]--; column_cnt[now.n][4]--; } } void print() { for(int i=1;i<=4;i++) printf("%s\n",mmap[i]+1); } int main() { int cas; scanf("%d",&cas); for(int i=1;i<=cas;i++) { myflag=0; memset(mmap,0,sizeof(mmap)); memset(row_cnt,0,sizeof(row_cnt)); memset(column_cnt,0,sizeof(column_cnt)); flag=1; for(int j=1;j<=4;j++) { scanf("%s",mmap[j]+1); for(int k=1;k<=4;k++) { if(mmap[j][k]=='*') { list[flag].m=j; list[flag].n=k; flag++; } else { row_cnt[j][mmap[j][k]-'0']++; column_cnt[k][mmap[j][k]-'0']++; } } } /* if(flag==1) { printf("Case #%d:\n",i); print(); continue; }*/ dfs(1); printf("Case #%d:\n",i); print(); } }