usaco_castle.cpp

usaco自己做的1到5章的代码

/*
ID:wangyuc2
PROG:castle
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <memory.h>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
ifstream fin ("castle.in");
ofstream fout ("castle.out");  

struct node{
       int num;
       int comp;
       }Node;
struct PT{
       int x,y;
       }pt;
int m,n,com,sum;
bool linkl[2501][2501];
node a[50][50];
int cap[2501];

void floodfill(int i,int j)
{
    queue<PT> q;
    PT p;
    p.x=i; p.y=j;
    q.push(p);   
	a[i][j].comp=com;
    while(!q.empty())
    {
       pt=q.front();
       q.pop();
       if(pt.y>=1 && !(a[pt.x][pt.y].num & 1) && a[pt.x][pt.y-1].comp<0 ) {p.x=pt.x; p.y=pt.y-1; q.push(p);a[pt.x][pt.y-1].comp=com;}
       if(pt.y<n-1 && !(a[pt.x][pt.y].num & 4)&& a[pt.x][pt.y+1].comp<0) {p.x=pt.x; p.y=pt.y+1; q.push(p);a[pt.x][pt.y+1].comp=com;}
       if(pt.x>=1 && !(a[pt.x][pt.y].num & 2)&& a[pt.x-1][pt.y].comp<0) {p.x=pt.x-1; p.y=pt.y; q.push(p);a[pt.x-1][pt.y].comp=com;}
       if(pt.x<m-1 && !(a[pt.x][pt.y].num & 8)&& a[pt.x+1][pt.y].comp<0) {p.x=pt.x+1; p.y=pt.y; q.push(p);a[pt.x+1][pt.y].comp=com;}
    }
}

int main()
{
   int i,j,k,maxi,maxj,max=0,maxr=0;
   fin>>n>>m;
   memset(linkl,false,sizeof(linkl));
   for(i=0;i<m;i++)
     for(j=0;j<n;j++)
     {
       fin>>a[i][j].num;
       a[i][j].comp=-1;
     }
   for(i=0;i<m;i++)
     for(j=0;j<n;j++)
     {
         if(a[i][j].comp<0) {com++;floodfill(i,j);}
     }
   for(i=0;i<m;i++)
     for(j=0;j<n;j++)
     {
         cap[a[i][j].comp]++;
         if(i>=1 && a[i][j].comp != a[i-1][j].comp) linkl[a[i][j].comp][a[i-1][j].comp]=true;
         if(i<m-1 && a[i+1][j].comp != a[i][j].comp) linkl[a[i][j].comp][a[i+1][j].comp]=true;
         if(j>=1 && a[i][j].comp != a[i][j-1].comp) linkl[a[i][j].comp][a[i][j-1].comp]=true;
         if(i<n-1 && a[i][j].comp != a[i][j+1].comp) linkl[a[i][j].comp][a[i][j+1].comp]=true;
     }
   for(i=0;i<=com;i++) if(cap[i]>max) max=cap[i];
   fout<<com<<endl<<max<<endl;  
   for(j=1;j<=com;j++)
	   for(i=com;i>j;i--)
		   if(linkl[i][j] && cap[i]+cap[j]>maxr) {maxr=cap[i]+cap[j]; maxi=i;maxj=j;}
	fout<<maxr<<endl;
	if(com==m*n){if(m>1) fout<<m<<' '<<1<<" N"<<endl;
				 else fout<<1<<' '<<1<<" E"<<endl;}
	else{
	  for(i=0;i<n;i++)
	  {
        bool flag=false;
		for(j=m-1;j>=0;j--)
		{
			if(i<n-1 && a[j][i].comp==maxi && a[j][i+1].comp==maxj || a[j][i].comp==maxj && a[j][i+1].comp==maxi)
			{ fout<<j+1<<' '<<i+1<<' '<<'E'<<endl; flag=true; break;}
			if(j>0 && a[j][i].comp==maxi && a[j-1][i].comp==maxj || a[j][i].comp==maxj && a[j-1][i].comp==maxi)
			{ fout<<j+1<<' '<<i+1<<' '<<'N'<<endl; flag=true; break;}
		}
		if(flag) break;
	  }
	}
  //  system("PAUSE");
    return 0;
}