Battle ships
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
Dear contestant, now you are an excellent navy commander, who is responsible of a tough mission currently.
Your fleet unfortunately encountered an enemy fleet near the South Pole where the geographical conditions are negative for both sides. The floating ice and iceberg blocks battleships move which leads to this unexpected engagement highly dangerous, unpredictable and incontrollable.
But, fortunately, as an experienced navy commander, you are able to take opportunity to embattle the ships to maximize the utility of cannons on the battleships before the engagement.
The target is, arrange as many battleships as you can in the map. However, there are three rules so that you cannot do that arbitrary:
A battleship cannot lay on floating ice
A battleship cannot be placed on an iceberg
Two battleships cannot be arranged in the same row or column, unless one or more icebergs are in the middle of them.
Your fleet unfortunately encountered an enemy fleet near the South Pole where the geographical conditions are negative for both sides. The floating ice and iceberg blocks battleships move which leads to this unexpected engagement highly dangerous, unpredictable and incontrollable.
But, fortunately, as an experienced navy commander, you are able to take opportunity to embattle the ships to maximize the utility of cannons on the battleships before the engagement.
The target is, arrange as many battleships as you can in the map. However, there are three rules so that you cannot do that arbitrary:
A battleship cannot lay on floating ice
A battleship cannot be placed on an iceberg
Two battleships cannot be arranged in the same row or column, unless one or more icebergs are in the middle of them.
Input
There is only one integer T (0<T<12) at the beginning line, which means following T test cases.
For each test case, two integers m and n (1 <= m, n <= 50) are at the first line, represents the number of rows and columns of the battlefield map respectively. Following m lines contains n characters iteratively, each character belongs to one of ‘#’, ‘*’, ‘o’, that symbolize iceberg, ordinary sea and floating ice.
For each test case, two integers m and n (1 <= m, n <= 50) are at the first line, represents the number of rows and columns of the battlefield map respectively. Following m lines contains n characters iteratively, each character belongs to one of ‘#’, ‘*’, ‘o’, that symbolize iceberg, ordinary sea and floating ice.
Output
For each case, output just one line, contains a single integer which represents the maximal possible number of battleships can be arranged.
Sample Input
2
4 4
*ooo
o###
**#*
ooo*
4 4
#***
*#**
**#*
ooo#
Sample Output
3
5
题意:
给出 T 组样例,输入 N 行 M 列。o 代表是可穿区域,# 代表不可穿区域,* 代表可放区域。问要求放物体到 * 上面,要求不允许放同一行或者同一列,# 不可以穿过,但是 o 是可以穿过的。输出最大能放的个数。
思路:
二分图。连通块建图。当时想到的是每个点之间建图,并没有想到用连通块。每个点建图的话,构出来的图有可能不是二分图,所以不能用点建图。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 55; char Map[MAX][MAX]; int cro[MAX][MAX], ver[MAX][MAX]; int n, m; int G[MAX * MAX][MAX * MAX]; int u; int linker[MAX * MAX]; bool vis[MAX * MAX]; void build () { memset(cro, -1, sizeof(cro)); memset(ver, -1, sizeof(ver)); u = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (Map[i][j] == '*' && cro[i][j] == -1) { int t = j; ++u; while (t <= m && Map[i][t] != '#') { if (Map[i][t] == '*') cro[i][t] = u; ++t; } j = t; } } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (Map[i][j] == '*' && ver[i][j] == -1) { int t = i; ++u; while (t <= n && Map[t][j] != '#') { if (Map[t][j] == '*') ver[t][j] = u; ++t; } } } } memset(G, 0, sizeof(G)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (Map[i][j] == '*') { int a = cro[i][j]; int b = ver[i][j]; G[a][b] = G[b][a] = 1; } } } } bool dfs (int x) { for (int i = 1; i <= u; ++i) { if (G[x][i] && !vis[i]) { vis[i] = 1; if (linker[i] == -1 || dfs(linker[i])) { linker[i] = x; return true; } } } return false; } int hungary () { int res = 0; memset(linker, -1, sizeof(linker)); for (int i = 1; i <= u; ++i) { memset(vis, 0, sizeof(vis)); if (dfs(i)) ++res; } return res; } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf(" %c", &Map[i][j]); } } build(); printf("%d\n", hungary() / 2); } return 0; }
相关推荐
B HDU 5093 Battle ships题意给出一个n行m列的图,*代表海域,o代表冰水,#代表冰山,要想在海域中放置船,保证船与船之间不能相互看到,之间
Guideline for set up Marine cyber enabled ships network
战舰 2名玩家的简单游戏。
简单React全栈 这是使用React,Node.js,Express和Webpack构建完整堆栈Web应用程序的样板。它还使用webpack-dev-server,eslint,prettier和babel进行配置。 介绍 是快速开始React开发的一种方法,它不需要构建配置...
#战舰当有两个玩家分别用一个棋盘初始化并且每个棋盘上放置了 5 艘船时,游戏就可以开始了。 默认情况下,玩家 1 先走,每次击球后,它会切换回合,直到获胜。 添加了一个 game_setup.rb 文件,该文件将游戏设置为...
Space Arcade - Enemy Ships.rar
Big Toon SciFi Star Ships.rar
控制领域很大牛人写的书,搞控制的必看!Khac Duc Do • Jie Pan这两个人一定得知道的。
famous_ships
作业说明 使用面向对象的设计方法来创建,开发和测试AdaShip(经典纸质战舰游戏的REPL.IT C ++计算机控制台版本/改编版)。 您应该采用敏捷和迭代的方法来分解,设计和开发游戏; 理想情况下,应尽早进行测试,然后...
战舰关于编写游戏可能是编程中最激动人心的任务之一。 开发您自己的流行“战舰游戏”版本,与您的朋友一起玩!学习成果您将了解开发诸如游戏之类的复杂程序的过程,并了解有关处理用户输入和处理错误的知识。
船ships的目标是在地图上可视化ships最新路线。对于用户安装从github安装remotes :: install_github( ' siddbhatia/ships ' ) 在本地安装git clone git@github....
BS ISO 24045-2021 Ships and marine technology — Adjustable roller-type chain stoppers.pdf
ISO 14726:2008 Ships and marine technology - Identification colo
ship gemogetry ship gemogetry
BS ISO 1704-2022 - Ships and marine technology — Stud-link function – Prin.pdf
新版完整标准 BS 24045-2021 Ships and marine technology — Adjustable roller-type chain stoppers.pdf
Indian Standard MECHANICAL VIBRATION -- GUIDELINES FOR THE MEASUREMENT,REPORTING AND EVALUATION OF VIBRATION WITH REGARD TO HABITABLITY ON PASSENGER AND MERCHANT SHIPS
最新完整版标准 ISO 24169-2022 Ships and marine technology - Fireproof watertight hatch covers.pdf
新版完整标准 BS ISO 24061-2021 Ships and marine technology — High holding power balance anchors.pdf