比赛 |
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;
}