最后一问输出：先输出最左边的，如果有多个则输出最靠下的。
/*
PROG : castle
LANG : C++
*/
# include <stdio.h>
# define N 55
const char ch[] = {'W', 'N', 'E', 'S'};
const int dx[] = {0,-1,0,1};
const int dy[] = {-1,0,1,0};
int n, m, cols;
int vis[N][N];
int r[N][N], c[N*N];
int Max(int x, int y)
{
return x>y ? x:y;
}
void init(void)
{
int i, j;
cols = 0;
scanf("%d%d", &m, &n);
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
{
vis[i][j] = 0;
scanf("%d", &r[i][j]);
}
}
int exist(int x, int y)
{
return (1<=x&&x<=n && 1<=y&&y<=m) ? 1:0;
}
void dfs(int x, int y, int *tot)
{
int d, nx, ny;
for (d = 0; d < 4; ++d)
{
if ((r[x][y]>>d) & 0x1) continue;
nx = x+dx[d];
ny = y+dy[d];
if (exist(nx, ny) && !vis[nx][ny])
{
vis[nx][ny] = cols;
++(*tot);
dfs(nx, ny, tot);
}
}
}
void solve(void)
{
int i, j, d, ii, jj, ti, tj, td, ans = 0, tmp;
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
{
if (!vis[i][j])
{
c[++cols] = 1;
vis[i][j] = cols;
dfs(i, j, &c[cols]);
}
}
printf("%d\n", cols);
for (i = 1; i <= cols; ++i)
ans = Max(ans, c[i]);
printf("%d\n",ans);
ans = 0;
for (j = 1; j <= m; ++j)
for (i = n; i >= 1; --i)
for (d = 0; d < 4; ++d)
{
if ((r[i][j]>>d)&0x1)
{
ii = i+dx[d], jj = j+dy[d];
if (exist(ii, jj) && (vis[i][j]^vis[ii][jj]))
{
tmp = c[vis[i][j]]+c[vis[ii][jj]];
if (ans < tmp)
{
ans = tmp;
ti = i, tj = j, td = d;
}
}
}
}
printf("%d\n", ans);
printf("%d %d %c\n", ti, tj, ch[td]);
}
int main()
{
freopen("castle.in", "r", stdin);
freopen("castle.out", "w", stdout);
init();
solve();
fclose(stdin);
fclose(stdout);
return 0;
}
posted on 2012-08-27 14:16
yajunw 阅读(119)
评论(0) 编辑 收藏 引用