用Floodfill來(lái)給每個(gè)module著色，統(tǒng)計(jì)一下各種顏色的module數(shù)目。
在拆墻的時(shí)候，由于要求最南和最西的，從下向上，從左到右找，這樣就可以滿足條件。
拆墻的時(shí)候，如果墻兩邊的顏色不一樣，則相加看是否最大。比最大值大則更新相應(yīng)信息。
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("castle.in");
ofstream?fout("castle.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
int?n,m;
int?c[50*50];
int?data[50][50];
int?colors[50][50];
int?color_cnt;
const?int?W?=?1;
const?int?N?=?2;
const?int?E?=?4;
const?int?S?=?8;
void?color(int?i,int?j,int?color);
void?solve()
{
????in>>m>>n;
????
????memset(c,0,sizeof(0));
????memset(colors,-1,sizeof(colors));
????color_cnt?=?0;
????for(int?i=0;i<n;++i)
????????for(int?j=0;j<m;++j){
????????????in>>data[i][j];
????????}
????for(int?i=0;i<n;++i)
????????for(int?j=0;j<m;++j){
????????????if(colors[i][j]==-1){
????????????????color(i,j,color_cnt++);
????????????}
????????}
????out<<color_cnt<<endl;
????int?largest?=?INT_MIN;
????for(int?i=0;i<color_cnt;++i){
????????largest?=?max(largest,c[i]);
????}
????out<<largest<<endl;
????largest?=?INT_MIN;
????int?walli,wallj;
????char?dir;
?????for(int?j=0;j<m;++j)
????????for(int?i=n-1;i>=0;--i)
????????{
?????????????if(i-1>=0){
????????????????if(?colors[i][j]!=colors[i-1][j]){
????????????????????if(?largest<c[colors[i][j]]+c[colors[i-1][j]]){
????????????????????????largest=c[colors[i][j]]+c[colors[i-1][j]];
????????????????????????walli?=?i;
????????????????????????wallj?=?j;
????????????????????????dir?=?'N';
????????????????????}
????????????????}
????????????}
????????????if(j+1<m){
????????????????if(?colors[i][j]!=colors[i][j+1]){
????????????????????if(largest<c[colors[i][j]]+c[colors[i][j+1]]){
????????????????????????largest?=?c[colors[i][j]]+c[colors[i][j+1]];
????????????????????????walli?=?i;
????????????????????????wallj?=?j;
????????????????????????dir?=?'E';
????????????????????}
????????????????}
????????????}
???????}
????out<<largest<<endl;
????out<<walli+1<<'?'<<wallj+1<<'?'<<dir<<endl;
}
void?color(int?i,int?j,int?clr)
{
???if(colors[i][j]!=-1)
??????return;
????colors[i][j]?=?clr;?
????c[clr]++;
????if((data[i][j]&S)==0&&(i+1<n)){
??????color(i+1,j,clr);?
????}
????if((data[i][j]&E)==0&&(j+1<m)){
????????color(i,j+1,clr);
????}
????if((data[i][j]&W)==0&&(j-1>=0)){
????????color(i,j-1,clr);
????}
????if((data[i][j]&N)==0&&(i-1>=0)){
????????color(i-1,j,clr);
????}
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 2868 KB]
Test 2: TEST OK [0.022 secs, 2868 KB]
Test 3: TEST OK [0.000 secs, 2868 KB]
Test 4: TEST OK [0.000 secs, 2868 KB]
Test 5: TEST OK [0.000 secs, 2868 KB]
Test 6: TEST OK [0.000 secs, 2872 KB]
Test 7: TEST OK [0.000 secs, 2872 KB]
Test 8: TEST OK [0.011 secs, 2868 KB]
All tests OK.