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