学习总结2.18

在原本基本的数船的基础上，增加了船不能畸形的要求，船只能是矩形，由此需要在dfs找船前确定是否有畸形船

.* ** *. ** ** .* ** *.

出现畸形船的情况如上图，即两艘船有一个交集时，此时就可以判断出bad placement

#include <stdio.h> #include<stdlib.h> #include<string.h> #define max 1005 int r,c; char ship[max][max]; int count=0; int dx[4]={-1,0,1,0}; int dy[4]={0,-1,0,1}; int row,line; void dfs(int x,int y){ ship[x][y]='.'; for(int i=0;i<4;i++){ row=x+dx[i]; line=y+dy[i]; if(row>=1&&row<=r&&line>=1&&line<=c&&ship[row][line]=='#'){ dfs(row,line); } } } int main() { scanf("%d %d",&r,&c); for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ scanf(" %c",&ship[i][j]); } } for(int i=1;i<r;i++){ for(int j=1;j<c;j++){ int cnt=0; if(ship[i][j]=='#') cnt++; if(ship[i+1][j]=='#') cnt++; if(ship[i][j+1]=='#') cnt++; if(ship[i+1][j+1]=='#') cnt++; if(cnt==3){//此时为相撞的情况 printf("Bad placement."); return 0; } } } for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ if(ship[i][j]=='#'){ dfs(i,j); count++; } } } printf("There are %d ships.",count); return 0; }

就当熟悉了bfs的函数

#include <stdio.h> #include<stdlib.h> #include<string.h> #define max 1005 typedef struct{ int x,y,step; }Node; Node queue[max*max];//数组模拟队列 int n; int fx,fy,ex,ey; int dx[4]={-1,0,1,0}; int dy[4]={0,-1,0,1}; char g[max][max]; int head=0,tail=0; void bfs(){ queue[tail++]=(Node){fx,fy,0}; g[fx][fy]='1'; while(head<tail){//队列不为空 Node cur=queue[head++]; if(cur.x==ex&&cur.y==ey){ printf("%d\n",cur.step); return; } for(int i=0;i<4;i++){ int row=cur.x+dx[i]; int line=cur.y+dy[i]; if(row>=1&&row<=n&&line>=1&&line<=n&&g[row][line]=='0'){ queue[tail++]=(Node){row,line,cur.step+1}; g[row][line]='1'; } } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf(" %c",&g[i][j]); } } scanf("%d %d %d %d",&fx,&fy,&ex,&ey); bfs(); return 0; }