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

暴力,用cin输入超时,用scanf刚好过

Posted by Idy002 at 2014-08-07 20:08:01 on Problem 1054
#include <cstdio>
#include <iostream>
#include <utility>
#include <algorithm>
#define isin(r,c) (1<=(r)&&(r)<=R&&1<=(c)&&(c)<=C)
#define x first
#define y second
using namespace std;

typedef pair<int,int> Pos;

int R, C, N;
int map[5001][5001];
Pos flatted[5001];


void input() {
	//cin>>R>>C>>N;
	scanf( "%d%d%d", &R, &C, &N );
	for( int i=1; i<=N; i++ ) {
		int r, c;
		//cin>>r>>c;
		scanf( "%d%d", &r, &c );
		map[r][c] = 1;
		flatted[i].x = r;
		flatted[i].y = c;
	}
	sort( flatted+1, flatted+1+N  );
}

bool cannot;
int dfs( int r, int c, int dr, int dc ) {
	int nr=r+dr, nc=c+dc;
	if( !isin(nr,nc) ) 
		return 0;
	if( map[nr][nc]==0 ) {
		cannot = true;
		return 0;
	}
	return dfs(nr,nc,dr,dc)+1;
}

void work() {
	int ans=0;
	cannot = false;
	for( int i=1; i<N; i++ )
		for( int j=i+1; j<=N; j++ ) {
			int r=flatted[i].x, c=flatted[i].y;
			int dr=flatted[j].x-r, dc=flatted[j].y-c;
			if( isin(r-dr,c-dc) ) continue;
			int cd=dfs(r,c,dr,dc)+1;
			if( cannot==true ) 
				cannot = false;
			else
				ans = max( ans, cd );
		}
	//if( ans<=2 ) cout<<"0"<<endl;
	//else cout<<ans<<endl;
	if( ans<=2 ) printf( "0\n" );
	else printf( "%d\n", ans );
}
int main() {
	input();
	work();
}

void show() {
	for( int r=1; r<=R; r++ ) {
		for( int c=1; c<=C; c++ )
			cerr<<map[r][c]<<" ";
		cerr<<endl;
	}
}

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