?? pku1856.cpp
字號(hào):
#include <stdio.h>
char ship[1001][1001];
int st[1001][1001];
int idst[5000][2];
int N, M;
int dis[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int in(int i, int j)
{
if (i >= 0 && i < N && j >= 0 && j < M)
{
return 1;
}
else
{
return 0;
}
}
void cls(int x, int y, int id)
{
int i, nextx, nexty;
st[x][y] = id;
for (i = 0; i < 8; i++)
{
nextx = x + dis[i][0];
nexty = y + dis[i][1];
if (in(nextx, nexty) && st[nextx][nexty] == -1)
{
cls(nextx, nexty, id);
}
}
}
int test(int p)
{
int sx, sy, ex, ey;
int i, j;
sx = idst[p][0];
sy = idst[p][1];
ex = sx + 1;
while (ex < N && st[ex][sy] == p) ex++;
ex--;
ey = sy + 1;
while (ey < M && st[sx][ey] == p) ey++;
ey--;
for (i = sx + 1; i <= ex; i++)
{
for (j = sy + 1; j <= ey; j++)
{
if (st[i][j] != p)
{
return 0;
}
}
}
if (in(sx - 1, sy))
{
for (i = sy; i <= sy; i++)
{
if (st[sx - 1][i] == p)
{
return 0;
}
}
}
if (in(ex + 1, sy))
{
for (i = sy; i <= ey; i++)
{
if (st[ex + 1][i] == p)
{
return 0;
}
}
}
if (in(sx, ey + 1))
{
for (i = sx; i <= ex; i++)
{
if (st[i][ey + 1] == p)
{
return 0;
}
}
}
if (in(sx, sy - 1))
{
for (i = sx; i <= ex; i++)
{
if (st[i][sy - 1] == p)
{
return 0;
}
}
}
if (in(sx - 1, sy - 1) && st[sx - 1][sy - 1] == p)
{
return 0;
}
if (in(sx - 1, ey + 1) && st[sx - 1][ey + 1] == p)
{
return 0;
}
if (in(ex + 1, sy - 1) && st[ex + 1][sy - 1] == p)
{
return 0;
}
if (in(ex + 1, ey + 1) && st[ex + 1][ey + 1] == p)
{
return 0;
}
return 1;
}
int main()
{
int i, j, count = 0, id;
while (scanf("%d%d", &N, &M) != -1)
{
if (N == 0 && M == 0)
{
break;
}
for (i = 0; i < N; i++)
{
scanf("%s", ship[i]);
}
for (i = 0; i < N; i++)
{
for (j = 0; j < M; j++)
{
if (ship[i][j] == '.')
{
st[i][j] = -2;
}
else
{
st[i][j] = -1;
}
}
}
for (i = 0, id = 0; i < N; i++)
{
for (j = 0; j < M; j++)
{
if (st[i][j] == -1)
{
cls(i, j, id);
idst[id][0] = i;
idst[id][1] = j;
id++;
}
}
}
for (i = 0, count = 0; i < id; i++)
{
if (test(i))
{
count++;
}
}
if (count == id)
{
printf("There are %d ships.\n", count);
}
else
{
printf("Bad placement.\n");
}
}
return 0;
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -