大体思路很容易想到,用邻接矩阵存储,floodfill之后
细节:
每个square墙的方向,一开始还想要不要写个结构体,4个方向的bool,能存下的.
仔细一看2^0,2^1,2^2,2^3,所以直接存储下来就行了,floodfill时,(x>>n)&1就好了
仔细阅读output中后面那一段文字,显然是在告诉我们搜索方向
for j = 0 to m-1
for i = n-1 downto 0
输出第一个答案就可以了,还有尝试东方和北方即可
再说floodfill,二维数组存储标号,先置为-2,还需要sum数组存储每个标号共有多少个房间
差不多分析好了,动工
-------------------------------------------------------------------------------------------
还以为floodfill很好写,关键是后面问题
结果floodfill各种出错,调了一个多小时,什么位运算搞错了,方向搞错了...
反而最后部分,写了个trysquare函数,用way记录NorE,很好写的...
一次AC~,算法和标程差不多
/*
ID: y7276571
PROG: castle
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn = 51;
int cas[maxn][maxn], wall[maxn][maxn], sum[maxn*maxn];
int m, n, compon = 0, maxsum = 0, biggest = 0, posx, posy, way;
bool floodfill(int x, int y)
{
if(cas[x][y] != -2) return false;
cas[x][y] = compon;
if(!((wall[x][y]>>0)&1) && floodfill(x, y-1)) sum[compon]++;
if(!((wall[x][y]>>1)&1) && floodfill(x-1, y)) sum[compon]++;
if(!((wall[x][y]>>2)&1) && floodfill(x, y+1)) sum[compon]++;
if(!((wall[x][y]>>3)&1) && floodfill(x+1, y)) sum[compon]++;
return true;
}
void trysquare(int x, int y)
{
if((wall[x][y]>>1)&1 && x > 0 && (cas[x][y] != cas[x-1][y]))
if(sum[cas[x][y]] + sum[cas[x-1][y]] > biggest)
{
biggest = sum[cas[x][y]] + sum[cas[x-1][y]];
posx = x;
posy = y;
way = 0;
}
if((wall[x][y]>>2)&1 && y < m-1 && (cas[x][y] != cas[x][y+1]))
if(sum[cas[x][y]] + sum[cas[x][y+1]] > biggest)
{
biggest = sum[cas[x][y]] + sum[cas[x][y+1]];
posx = x;
posy = y;
way = 1;
}
}
int main()
{
freopen("castle.in", "r", stdin);
freopen("castle.out", "w", stdout);
cin >> m >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cas[i][j] = -2;
for(int i = 0; i < n*m; i++) sum[i] = 1;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> wall[i][j];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(floodfill(i, j)) compon++;
for(int i = 0; i < compon; i++)
if(sum[i] > maxsum) maxsum = sum[i];
//question 1 and 2 have been finished
//find max sum
for(int j = 0; j < m; j++)
for(int i = n-1; i >= 0; i--)
trysquare(i,j);
//cout all the answers
cout << compon << endl <<maxsum << endl << biggest << endl;
cout << posx+1 << " " << posy+1 << " ";
if(way == 0) cout << "N" << endl;
else cout << "E" << endl;
return 0;
}
原文链接: https://www.cnblogs.com/shixuehunk/archive/2012/02/12/2347835.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/41474
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
