学习总结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;
}