Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
终于ac了。。。。其实不是搜索,应该迭代!!rt 一下是code: /* ID: talenth1 PROG: p1099 LANG: C++ */ #include<iostream> #include<cstdlib> #include<cstring> #include<cmath> #define maxn 500 using namespace std; int dh[]={0,-1,0,0,1},dl[]={0,0,-1,1,0}; int n,szero,a[maxn][maxn][5],stu1[maxn][maxn],stu2[maxn][maxn]; void datain() { int tmp; memset(a,0,sizeof(a)); memset(stu1,0,sizeof(stu1)); memset(stu2,0,sizeof(stu2)); szero=0; for(int i=1;i<=n;i++){ a[0][i][4]=1; a[n+1][i][1]=1; a[i][n+1][2]=-1; a[i][0][3]=-1; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ scanf("%d",&tmp); if(tmp==1){ stu1[i][j]=2; stu2[i][j]=2; a[i][j][1]=-1; a[i][j][2]=1; a[i][j][3]=1; a[i][j][4]=-1; } if(tmp==-1){ stu1[i][j]=2; stu2[i][j]=2; a[i][j][1]=1; a[i][j][2]=-1; a[i][j][3]=-1; a[i][j][4]=1; } if(tmp==0)szero++; } } void output() { char list[maxn][maxn]; memset(list,' ',sizeof(list)); for(int i=0;i<=4*n+2;i++){ list[i][0]='*'; list[0][i]='*'; list[4*n-2][i]='*'; list[i][4*n+2]='*'; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ int hi=4*i-3; int li=4*j-1; list[hi][li]='O'; if(a[i][j][1]==1){ list[hi-1][li]='|'; list[hi-2][li]='H'; } if(a[i][j][2]==1){ list[hi][li-1]='-'; list[hi][li-2]='H'; } if(a[i][j][3]==1){ list[hi][li+1]='-'; list[hi][li+2]='H'; } if(a[i][j][4]==1){ list[hi+1][li]='|'; list[hi+2][li]='H'; } } for(int i=0;i<=4*n-2;i++){ for(int j=0;j<=4*n+2;j++) printf("%c",list[i][j]); printf("\n"); } } void deal(int h,int l) { if(stu1[h][l]==2) for(int i=1;i<=4;i++) if(!a[h][l][i])a[h][l][i]=-1; if(stu2[h][l]==2) for(int i=1;i<=4;i++) if(!a[h][l][i])a[h][l][i]=1; } bool judge(int h,int l) { if(stu1[h][l]>=2){ deal(h,l); return true; } if(stu2[h][l]>=2){ deal(h,l); return true; } if(a[h][l][1]==1){a[h][l][4]=-1;stu2[h][l]++;} if(a[h][l][4]==1){a[h][l][1]=-1;stu2[h][l]++;} if(a[h][l][2]==1){a[h][l][3]=-1;stu2[h][l]++;} if(a[h][l][3]==1){a[h][l][2]=-1;stu2[h][l]++;} if(stu1[h][l]>=2){ deal(h,l); return true; } if(stu2[h][l]>=2){ deal(h,l); return true; } return false; } void work() { int solved=0; bool change=true; while(solved<szero&&change){ change=false; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(!judge(i,j)) for(int k=1;k<=4;k++){ int hi=i+dh[k]; int li=j+dl[k]; if(a[hi][li][5-k]&&!a[i][j][k]){ a[i][j][k]=-a[hi][li][5-k]; if(a[i][j][k]>0)stu1[i][j]++; if(a[i][j][k]<0)stu2[i][j]++; if(judge(i,j)){ solved++; change=true; }//if stu }//if a }//for }//while output(); } int main() { freopen("p1099.in","r",stdin); freopen("p1099.out","w",stdout); int t=0; while(1){ scanf("%d",&n); if(n==0)break; t++; printf("Case %d:\n\n",t); datain(); work(); printf("\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator