題意是這樣，一個海面上有N條船，用長方形表示。海域中#代表有船的格子，.代表沒船的格子。統(tǒng)計共有多少條船。
如果兩條船有接觸的話（包括頂點接觸），則判為不合法。
說下判斷不合法的情況如何判斷吧。
DFS或者BFS求聯(lián)通分量的時候，維護左上角坐標（r1,c1)和右下角坐標(r2,c2)，再統(tǒng)計出聯(lián)通分量中的網(wǎng)格數(shù)num。如果(r2-r1+1)*(c2-c1+1)!=num，就不合法。
開始我沒注意不能夠頂角相連，所以在算聯(lián)通分量的時候僅僅向(r-1,c) (r+1,c) (r,c-1) (r,c+1)轉移，事實上還要向(r-1,c-1) (r+1,c+1) (r-1,c+1) (r+1,c-1)轉移。細心啊細心，regional被這種題粉掉就要撞墻了
貼代碼
1
# include <iostream>
2# include <cstring>
3# include <cstdio>
4# include <queue>
5using namespace std;
6bool used[1200000];
7char map[1001][1002];
8# define encode(a,b) (((a)<<10)|(b))
9queue<int> q;
10int main()
11
{
12
int r,c,i,j;
13 while(true)
14
{
15 scanf("%d%d",&r,&c);
16 if(!r&&!c) break;
17 for(i=0;i<r;i++)
18 scanf("%s",map[i]);
19 int res=0;
20 bool flag=true;
21 memset(used,0,sizeof(used));
22 for(i=0;i<r&&flag;i++)
23 for(j=0;j<c&&flag;j++)
24 if(map[i][j]=='#')
25 {
26 int r1=0xfffffff,c1=0xfffffff,r2=-1,c2=-1,num=0;
27 while(!q.empty()) q.pop();
28 q.push(encode(i,j));
29 used[encode(i,j)]=true;
30 while(!q.empty())
31 {
32 int tr=q.front()>>10,tc=q.front()&1023;
33 q.pop();
34 num++;
35 map[tr][tc]='.';
36 if(tr<r1||tr==r1&&tc<c1) r1=tr,c1=tc;
37 if(tr>r2||tr==r2&&tc>c2) r2=tr,c2=tc;
38 if(tr+1<r&&map[tr+1][tc]=='#'&&!used[encode(tr+1,tc)])
39 {
40 q.push(encode(tr+1,tc));
41 used[encode(tr+1,tc)]=true;
42
}
43 if(tr-1>=0&&map[tr-1][tc]=='#'&&!used[encode(tr-1,tc)])
44 {
45 q.push(encode(tr-1,tc));
46 used[encode(tr-1,tc)]=true;
47 }
48 if(tc+1<c&&map[tr][tc+1]=='#'&&!used[encode(tr,tc+1)])
49 {
50 q.push(encode(tr,tc+1));
51 used[encode(tr,tc+1)]=true;
52 }
53 if(tc-1>=0&&map[tr][tc-1]=='#'&&!used[encode(tr,tc-1)])
54 {
55 q.push(encode(tr,tc-1));
56 used[encode(tr,tc-1)]=true;
57 }
58 if(tc-1>=0&&tr-1>=0&&map[tr-1][tc-1]=='#'&&!used[encode(tr-1,tc-1)])
59 {
60 q.push(encode(tr-1,tc-1));
61 used[encode(tr-1,tc-1)]=true;
62 }
63 if(tc-1>=0&&tr+1<r&&map[tr+1][tc-1]=='#'&&!used[encode(tr+1,tc-1)])
64 {
65 q.push(encode(tr+1,tc-1));
66 used[encode(tr+1,tc-1)]=true;
67 }
68 if(tc+1<c&&tr-1>=0&&map[tr-1][tc+1]=='#'&&!used[encode(tr-1,tc+1)])
69 {
70 q.push(encode(tr-1,tc+1));
71 used[encode(tr-1,tc+1)]=true;
72 }
73 if(tc+1<c&&tr+1<r&&map[tr+1][tc+1]=='#'&&!used[encode(tr+1,tc+1)])
74 {
75 q.push(encode(tr+1,tc+1));
76 used[encode(tr+1,tc+1)]=true;
77 }
78 }
79 if((r2-r1+1)*(c2-c1+1)!=num) flag=false;
80 else res++;
81 }
82 if(flag) printf("There are %d ships.\n",res);
83 else printf("Bad placement.\n");
84 }
85 return 0;
86
}
87
88