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

waaao先生真不容易啊!

Posted by yc5_yc at 2012-12-30 22:50:23 on Problem 1175
六次wa,鏖战超过40分钟,终于AC了
贴一下此弱智的代码:
#include <cstdio>//事实证明,map是可以过的,但是细节太多了。。。。。。
#include <cmath>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;
const int NMax=150;
int N,M,F[NMax][NMax],num[NMax][NMax],mini[NMax*NMax],maxi[NMax*NMax],minj[NMax*NMax],maxj[NMax*NMax],F1[NMax][NMax];
char map1[NMax][NMax];
void DFS(int x,int y,int color) {
	F[x][y]=color;
	mini[color]=min(x,mini[color]);
	minj[color]=min(y,minj[color]);
	maxi[color]=max(x,maxi[color]);
	maxj[color]=max(y,maxj[color]);
	if(x-1>=0&&!F[x-1][y]&&map1[x-1][y]=='1') DFS(x-1,y,color);
	if(x+1<M&&!F[x+1][y]&&map1[x+1][y]=='1') DFS(x+1,y,color);
	if(y-1>=0&&!F[x][y-1]&&map1[x][y-1]=='1') DFS(x,y-1,color);
	if(y+1<N&&!F[x][y+1]&&map1[x][y+1]=='1') DFS(x,y+1,color);
	if(x-1>=0&&y-1>=0&&!F[x-1][y-1]&&map1[x-1][y-1]=='1') DFS(x-1,y-1,color);
	if(x+1<M&&y-1>=0&&!F[x+1][y-1]&&map1[x+1][y-1]=='1') DFS(x+1,y-1,color);
	if(x+1<M&&y+1<N&&!F[x+1][y+1]&&map1[x+1][y+1]=='1') DFS(x+1,y+1,color);
	if(x-1>=0&&y+1<N&&!F[x-1][y+1]&&map1[x-1][y+1]=='1') DFS(x-1,y+1,color);
}
double POW(double a,int b){double ret=1.0;while(b--) ret*=a;return ret;}
void change(int c0,int c1) {
	for(int i=0;i<M;i++) 
		for(int j=0;j<N;j++) if(F[i][j]==c0) F1[i][j]=c1;
}
map<int,int> M1;
int main()
{
	memset(F,0,sizeof(F));
	scanf("%d%d",&N,&M);
	for(int i=0;i<M;i++) scanf("%s",map1[i]);
	int cc=0;
	for(int i=0;i<M;i++)
		for(int j=0;j<N;j++) if(map1[i][j]=='1'&&!F[i][j]){
			cc++;
			mini[cc]=minj[cc]=100000000;maxi[cc]=maxj[cc]=-1;
			DFS(i,j,cc);
		}
	int cc1=0;
	for(int c=1;c<=cc;c++) {
		double midx=(double)(mini[c]+maxi[c])/2,midy=(double)(minj[c]+maxj[c])/2;
		//printf("%d %d %d %d\n",mini[c],maxi[c],minj[c],maxj[c]);
		double cnt=0;
		for(int i=mini[c];i<=maxi[c];i++)
			for(int j=minj[c];j<=maxj[c];j++) if(F[i][j]==c)
				for(int i1=mini[c];i1<=maxi[c];i1++)
					for(int j1=minj[c];j1<=maxj[c];j1++) if(F[i1][j1]==c) {
						cnt+=sqrt(POW(double(i-i1),2)+POW((double)(j-j1),2));
					}
		//printf("%lf\n",cnt);
		cnt=(int)(cnt*100);
		//printf("%lf\n",cnt);
		if(!M1[(int)cnt]) M1[(int)cnt]=++cc1;
		change(c,M1[(int)cnt]);
	}
	//puts("");
	//for(int i=0;i<M;i++) {
	//	for(int j=0;j<N;j++)printf("%d",F1[i][j]);
	//	puts("");
	//}
	//puts("");
	for(int i=0;i<M;i++) {
		for(int j=0;j<N;j++) if(F1[i][j])printf("%c",(char)(F1[i][j]+'a'-1));else printf("0");
		puts("");
	}
	getchar();getchar();
	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