题目传送门
思路
肯定食用dfs啦。。。
但关键是两条船接触了怎么判断呢？？
上图：
可以发现一下规律
当两条船接触时，必有一条直线连续穿过两条船
当一条船不与另一条船接触时，没有一条直线连续穿过两条船
所以只需要在每一次碰见一条船的一部分（一条船内每个点都要拓展一遍）时，将其沿右上、左下分别拓展一遍，边拓展边用sum前缀和check一遍就好啦。。。。
核心代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//码风很丑，勿喷 int k=1; while(a[i+k][j+k]==1) k++;//找到最左下的一个点（即连线段的另一个端点） --k;//别忘了再加回来 int hh=sum[i+k][j+k]-sum[i-1][j]-sum[i][j-1]+sum[i-1][j-1];//前缀和 ++k; if(hh<k*k){//前缀和必须是k*k（一个正方形） puts("Bad placement."); return 0;//强制结束 }//沿右上 k=1;//清零 while(a[i+k][j-k]==1) ++k;//找到最左下的一个点（即连线段的另一个端点） --k; hh=sum[i+k][j]-sum[i-1][j]-sum[i+k][j-k-1]+sum[i-1][j-k-1];//前缀和 ++k;//别忘了再加回来 if(hh<k*k){//前缀和必须是k*k（一个正方形） puts("Bad placement."); return 0;//强制结束 }//沿左下 |
如果没有接触的话，可以直接dfs啦。。。代码简洁：
|
1 2 3 4 5 6 7 8 |
void dfs(int x,int y){ if(vis[x][y]==1) return ;//如果已经拓展过直接退出 vis[x][y]=1;//标记 if(a[x][y+1]==1) dfs(x,y+1);//向四个方向拓展，标记为此船 if(a[x-1][y]==1) dfs(x-1,y); if(a[x+1][y]==1) dfs(x+1,y); if(a[x][y-1]==1) dfs(x,y-1); } |
所有代码：（非常“简洁”。。。）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include<bits/stdc++.h> using namespace std; inline int read(){ int ret=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();} while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar(); return ret*f; }//丑陋的读优 void write(int x){ if(x<0){ putchar('-'); write(-x); return ; } if(x<10) putchar(x+'0'); else{ write(x/10); putchar(x%10+'0'); } }//丑陋的输优 int n,m,a[1010][1010],sum[1010][1010]; int vis[1010][1010],ans; void dfs(int x,int y){ if(vis[x][y]==1) return ; vis[x][y]=1; if(a[x][y+1]==1) dfs(x,y+1); if(a[x-1][y]==1) dfs(x-1,y); if(a[x+1][y]==1) dfs(x+1,y); if(a[x][y-1]==1) dfs(x,y-1); }//丑陋的dfs int main(){ n=read();m=read(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ char ch;cin>>ch; if(ch=='#') a[i][j]=1; } }//读入 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; } }//前缀和 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]==1){ int k=1; while(a[i+k][j+k]==1) k++; --k; int hh=sum[i+k][j+k]-sum[i-1][j]-sum[i][j-1]+sum[i-1][j-1]; ++k; if(hh<k*k){ puts("Bad placement."); return 0; } k=1; while(a[i+k][j-k]==1) ++k; --k; hh=sum[i+k][j]-sum[i-1][j]-sum[i+k][j-k-1]+sum[i-1][j-k-1]; ++k; if(hh<k*k){ puts("Bad placement."); return 0; } }//不想再提了。。。判断船只是否接触 } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]==1&&vis[i][j]==0){ ++ans; dfs(i,j); }//dfs统计答案 } } cout<<"There are "; write(ans); cout<<" ships.";putchar('\n');//输出 return 0;//结束。。。。 } /************************* 用时: 102ms / 内存: 5152KB 代码：1.63KB C++ By yuzhengxi **************************/ |
