Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

终于ac了。。。。其实不是搜索,应该迭代!!

Posted by talenth1 at 2011-01-01 18:22:48 on Problem 1099
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator