比赛 20140714下午练习 评测结果 AAAAAAAA
题目名称 城堡 最终得分 100
用户昵称 1azyReaper 运行时间 0.012 s
代码语言 C++ 内存使用 7.27 MiB
提交时间 2014-07-14 15:57:27
显示代码纯文本
#include <fstream>
#include <cstdio>
#include <queue>
#include <cstdlib>
#include <algorithm>
using namespace std;
class node
{
	public:
	bool e,w,s,n;
	int a;
};
node board[999][999];
ifstream fin("castle.in");
ofstream fout("castle.out");
int space[99999]={0},sum=1;
int remax=-1,rex,rey;
char redir;
int m,n;
int input()
{
	int i,j,temp;
	fin>>n>>m;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			board[i][j].a=0;
			fin>>temp;
			board[i][j].w=(temp%2==0)?0:1,temp/=2;
			board[i][j].n=(temp%2==0)?0:1,temp/=2;
			board[i][j].e=(temp%2==0)?0:1,temp/=2;
			board[i][j].s=(temp%2==0)?0:1,temp/=2;
		}
	}
	return 0;
}
int floodfill(int x,int y,int p)
{
	queue<pair<int,int> > s;
	s.push(make_pair(x,y)),board[x][y].a=p;
	int x1,y1;
	while(!s.empty())
	{
		x1=s.front().first,y1=s.front().second,space[p]++,s.pop();
		if(board[x1][y1].e==0&&board[x1][y1+1].a==0) 
			s.push(make_pair(x1,y1+1)),board[x1][y1+1].a=p;
		if(board[x1][y1].w==0&&board[x1][y1-1].a==0) 
			s.push(make_pair(x1,y1-1)),board[x1][y1-1].a=p;
		if(board[x1][y1].n==0&&board[x1-1][y1].a==0) 
			s.push(make_pair(x1-1,y1)),board[x1-1][y1].a=p;
		if(board[x1][y1].s==0&&board[x1+1][y1].a==0) 
			s.push(make_pair(x1+1,y1)),board[x1+1][y1].a=p;
	}
	return 0;
}
int floodfill()
{
	int p=1,i,j;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			if(board[i][j].a==0) floodfill(i,j,p++);
		}
	}
	sum=p-1;
	return 0;
}
int largestroom()
{
	int i,max=-1;
	for(i=1;i<=sum;i++) if(space[i]>max) max=space[i];
	return max;
}
int remove()
{
	int i,j,temp1,temp2;
	for(j=0;j<n;j++)
	{
		for(i=m-1;i>=0;i--)
		{
			if(board[i][j].n&&board[i-1][j].a!=board[i][j].a)
			{
				temp1=board[i-1][j].a,temp2=board[i][j].a;
				if(space[temp1]+space[temp2]>remax) remax=space[temp1]+space[temp2],rex=i,rey=j,redir='N';
			}
			if(board[i][j].e&&board[i][j+1].a!=board[i][j].a)
			{
				temp1=board[i][j+1].a,temp2=board[i][j].a;
				if(space[temp1]+space[temp2]>remax) remax=space[temp1]+space[temp2],rex=i,rey=j,redir='E';
			}
		}
	}
	return 0;
}
int main(){
	int o;
	input();
	floodfill();
	remove();
	fout<<sum<<endl;
	fout<<largestroom()<<endl;
	fout<<remax<<endl;
	fout<<rex+1<<' '<<rey+1<<' '<<redir<<endl;
	fin.close();
	fout.close();
	return 0;
}