作业1-224——P1331 海战

2024-03-02 06:44
文章标签 作业 224 海战 p1331

本文主要是介绍作业1-224——P1331 海战,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 思路

深搜的方式,让它只遍历矩形块,然后在下面的遍历中判断是否出现矩形块交叉,但是很难实现,然后发现可以通过在遍历过程中判断是否合法。

参考代码

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1010;

char g[N][N];
int st[N][N];
int r, c;

int dx[] = {-1, -1, 1, 1, 0, 1, 0, -1};
int dy[] = {-1, 1, -1, 1, 1, 0, -1, 0};

int dfs(int x, int y){
    st[x][y] = 1;
    for(int i = 0; i < 4; i ++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >= 0 && ny >= 0 && nx < r && ny < c)
            if(g[nx][ny] == '.')
                if(g[x][ny] == '#' && g[nx][y] == '#') return 0;
    }
    
    for(int i = 0; i < 4; i ++){
        int nx = x + dx[i + 4], ny = y + dy[i + 4];
        if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
        if(st[nx][ny] || g[nx][ny] == '.') continue;
        if(!dfs(nx, ny)) return 0;
    }
    
    return 1;
}

int main(){
    cin >> r >> c;
    
    for(int i = 0; i < r; i ++) cin >> g[i];
    
    int res = 0;
    
    for(int i = 0; i < r; i ++)
        for(int j = 0; j < c; j ++)
            if(!st[i][j] && g[i][j] == '#')
                if(dfs(i, j)) res ++;
                else{
                    puts("Bad placement.");
                    return 0;
                }
    
    printf("There are %d ships.", res);
    return 0;
}


 

这篇关于作业1-224——P1331 海战的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/765248

相关文章

作业提交过程之HDFSMapReduce

作业提交全过程详解 (1)作业提交 第1步:Client调用job.waitForCompletion方法,向整个集群提交MapReduce作业。 第2步:Client向RM申请一个作业id。 第3步:RM给Client返回该job资源的提交路径和作业id。 第4步:Client提交jar包、切片信息和配置文件到指定的资源提交路径。 第5步:Client提交完资源后,向RM申请运行MrAp

Java高级Day38-网络编程作业

112.网络编程作业 //1.使用字符流的方式,编写一个客户端程序和服务器端程序//2.客户端发送"name",服务器端接收到后,返回"我是nova"//3.客户端发送"hobby",服务器端接收到后,返回"编写java程序"//4.不是这两个问题,回复"你说啥呢"​​===============//客户端//===============public class SocketT

0906作业+思维导图梳理

一、作业: 1、创捷一个类似于qq登录的界面 1)源代码 #include "widget.h"#include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget){ui->setupUi(this);//QPushbutton:登录、退出this->join = new QP

2024.9.6 作业

1> 手写unique_ptr指针指针 #include <iostream>using namespace std;template <typename T>class my_unique_ptr{public:explicit my_unique_ptr(T *p = nullptr) noexcept // 构造函数{ptr = p;}~my_unique_ptr() noexcep

9月6号作业

1:.h文件 #ifndef MAINWINDOW_H #define MAINWINDOW_H #include <QMainWindow> #include <QWidget> #include<QIcon> //图标类 #include<QLabel> //标签类 #include<QMovie> //动图类 #include<QLineEdit> //行编辑器类

Flink实例(六十九): flink 作业提交(四)总结

独立集群提交 # 启动集群bin/start-cluster.sh# 提交job./bin/flink run ./examples/batch/WordCount.jar --input hdfs:/user/yuan/input/wc.count --output hdfs:/user/yuan/swwwttt yarn session # 启动集群./bin/

【#第三期实战营闯关作业 ## 茴香豆:企业级知识库问答工具】

今天学习了《 茴香豆:企业级知识库问答工具》这一课,对大模型的应用有了更深得认识。以下是记录本课实操过程及截图: 搭建茴香豆虚拟环境: 输入以下命令 ``studio-conda -o internlm-base -t huixiangdou 成功安装虚拟环境截图 安装茴香豆 cd /root 克隆代码仓库 git clone https://github.com/internlm/h

Quartz 作业调度器

1、Quartz  java实现  注:这里使用的是Quartz1.6.5版本(包:quartz-1.6.5.jar)   [java]  view plain copy //测试main函数   //QuartzTest.java   package quartzPackage;         import java.text.SimpleDateFormat

清华MEM作业-利用管理运筹学的分析工具slover求解最优解的实现 及 通过使用文件或者套节字来识别进程的fuser命令

一、清华MEM作业-利用管理运筹学的分析工具slover求解最优解的实现         最近又接触了一些线性求解的问题,以前主要都是在高中数学里接触到,都是使用笔算,最后通过一些函数式得出最小或者最大值,最近的研究生学业上接触到了一个Excel solver分析工具,对这种线性求最优解的问题感觉使用起来真是得心应手。在使用这个工具前,EXCEL里需要先装上solver工具,装起来很也简单,网上

opencv作业

作业下载地址: 链接:http://pan.baidu.com/s/1qYQnbkw 密码:v7y9