Posted on 2007-06-19 22:03
ZelluX 閱讀(313)
評論(0) 編輯 收藏 所屬分類:
Algorithm
Wrong Answer了半天發現原來是m - 1打成m + 1了。。。
/*
PROG: castle
ID: 06301031
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
enum Direction {WEST = 0, NORTH = 1, EAST = 2, SOUTH = 3};
// The directions corresponding to the following steps are
// West(0), North(1), East(2) and South(3).
const int dx[] = {0, -1, 0, 1};
const int dy[] = {-1, 0, 1, 0};
int region[50][50];
int colors[50 * 50];
int maze[50][50];
bool canGo(int value, int dirx)
{
int base = 1;
for (int i = 0; i < dirx; i++)
base *= 2;
return ((base & value) == 0);
}
void floodfill(int x, int y, int color)
{
if (region[x][y] < 0)
{
region[x][y] = color;
colors[color]++;
}
//cout << "now paint " << x << ',' << y << endl;
for (int i = 0; i < 4; i++) // dirction
{
if (canGo(maze[x][y], i) && region[x + dx[i]][y + dy[i]] < 0)
{
floodfill(x + dx[i], y + dy[i], color);
}
}
}
int main()
{
ifstream fin("castle.in");
ofstream fout("castle.out");
int m, n;
fin >> n >> m;
for (int i = 0; i < m; i++)
for (int j= 0; j < n; j++)
{
fin >> maze[i][j];
region[i][j] = -1;
}
int colorCount = 0;
int maxCount = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (region[i][j] < 0)
{
colors[colorCount] = 0;
floodfill(i, j, colorCount);
if (maxCount < colors[colorCount])
maxCount = colors[colorCount];
// for (int ii = 0; ii < m; ii++) {
// for (int jj = 0; jj < n; jj++)
// cout << (region[ii][jj] >= 0 ? region[ii][jj] : ' ');
// cout << endl;
// }
// cout << i << ',' << j << ':' << colorCount << ' ' << colors[colorCount] << endl;
colorCount++;
}
fout << colorCount << endl;
fout << maxCount << endl;
int maxCombine = 0, maxD, maxI, maxJ;
for (int j = 0; j < n; j++)
for (int i = m - 1; i >= 0; i--)
for (int d = 1; d < 3; d++)
{
int nx = i + dx[d];
int ny = j + dy[d];
if (nx < 0 || nx >= m || ny < 0 || ny >= n)
continue;
if (region[nx][ny] != region[i][j])
{
if (maxCombine < colors[region[nx][ny]] + colors[region[i][j]])
{
maxCombine = colors[region[nx][ny]] + colors[region[i][j]];
maxD = d;
maxI = i;
maxJ = j;
}
}
}
fout << maxCombine << endl;
fout << maxI + 1 << ' ' << maxJ + 1 << ' ';
switch (maxD)
{
case 0: fout << 'W' << endl;
break;
case 1: fout << 'N' << endl;
break;
case 2: fout << 'E' << endl;
break;
case 3: fout << 'S' << endl;
break;
}
return 0;
}