列表

详情


NC14698. 模拟战役

描述

齐齐和司机在玩单机游戏《红色警戒IV》,现在他们的游戏地图被划分成一个n*m的方格地图。齐齐的基地在最上方的4行格内,司机的基地在最下方的4行格内。他们只有一种攻击方式:远程大炮,相关属性如下:
1、    大炮可以打到地图的任意一个位置。
2、    双方每次必须动用本方的一门大炮攻击,齐齐先手,双方交替进行攻击。
3、    一方大炮只能攻击另一方大炮,不能攻击本方或强制攻击未获得视野的地区。
4、    被一方大炮击中的另一方大炮会产生以攻击点为中心3*3的波及区域,波及区域内如果有其他大炮则也会产生3*3的波及区域。
5、    两方的基地相距很远,所以不存在攻打敌方大炮时波及到本方大炮的情况。
齐齐偷偷开了“间谍卫星”,所以他能看到司机的大炮部署,司机则无视野。但如果齐齐做出攻击,司机会立即获取到发动攻击的大炮的视野,并在回合开始时动用大炮(如果存在的话)将其摧毁(摧毁后可能产生的连锁不计入视野)。
现在给出齐齐和司机的大炮部署,问齐齐在选择最优的策略下,在摧毁所有司机的大炮后可以保留最多几门本方大炮。

输入描述

第1行输入一个整数m,表示地图的宽度。
第2-5行,每行输入一串长度为m的字符串,代表司机的大炮部署。(大炮为"*"号,空地为“.”号)
第6-9行,每行输入一串长度为m的字符串,代表齐齐的大炮部署。(大炮为"*"号,空地为“.”号)
数据保证:0<m≤100

输出描述

输出一行,一个整数。代表摧毁所有司机的大炮后最多保留几门大炮。如果不能摧毁所有司机的大炮,则输出-1。

示例1

输入:

3
...
.*.
..*
*..
*..
.**
...
*.*

输出:

4

示例2

输入:

3
*..
..*
...
...
...
...
.*.
...

输出:

-1

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 612K, 提交时间: 2020-05-15 14:37:09

#include<bits/stdc++.h>
using namespace std;
const int N=1100;
int size[N];
char s[N][N];
int vis[N][N];
int dx[8]={0,1,0,-1,-1,1,1,-1};
int dy[8]={1,0,-1,0,1,1,-1,-1};
int m,cnt;
int a[N],b[N],tot,tot1;
void   dfs(int x,int y,int &ans,int k)
{
	if(s[x][y]=='.') return ;
	vis[x][y]=true;
	for(int i=0;i<8;i++)
	{
		int xx=dx[i]+x;
		int yy=dy[i]+y;
		if(xx<k||xx>=k+4||yy<0||y>=m||vis[xx][yy]) continue;
		vis[xx][yy]=true;
		if(s[xx][yy]=='*') ans++;
		dfs(xx,yy,ans,k);

	}
}
int main()
{
	cin>>m;
	for(int i=0;i<8;i++) cin>>s[i];
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(s[i][j]=='*'&&!vis[i][j])
			{
				cnt=1;
				dfs(i,j,cnt,0);	
				a[++tot]=cnt;
			}
		}
	}
	for(int i=4;i<8;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(s[i][j]=='*'&&!vis[i][j])
			{
				cnt=1;
				dfs(i,j,cnt,4);
				b[++tot1]=cnt;
			}
		}
	}
	if(tot1<tot) cout<<-1<<endl;
	else
	{

		sort(b+1,b+1+tot1);
		int ans=0;
		for(int i=tot;i<=tot1;i++) ans+=b[i];
		cout<<ans<<endl;
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 408K, 提交时间: 2022-12-25 19:20:18

#include <bits/stdc++.h>
#define n 105
using namespace std;
char mp[8][n];
int m,dr[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
int a[n];
int dfs(int i,int j,int l)
{
	int res=0;
	if(mp[i][j]=='*')
	{
		res++;
		mp[i][j]='.';
		for(int k=0;k<8;k++)
		{
			int x=i+dr[k][0];
			int y=j+dr[k][1];
			if(x>=l-4&&x<l&&y>=0&&y<m)
				res+=dfs(x,y,l);
		}
		return res;
	}
	return 0;
}

int main()
{
	int sum=0;
    cin >> m;
    for(int i=0;i<8;i++)
    	for(int j=0;j<m;j++)
    		cin >> mp[i][j];
    int qiqi=0,siji=0;
    for(int i=0;i<4;i++)
    	for(int j=0;j<m;j++)
    		if(dfs(i,j,4)) siji++;
	for(int i=4;i<8;i++)
	{
		for(int j=0;j<m;j++)
		{
			int num=dfs(i,j,8);
			if(num) a[qiqi++]=num;
		}
	}
	if(qiqi<siji)
	{
		cout << -1 << endl;
	}
	else
	{
		sort(a,a+qiqi);
		for(int i=siji>0?siji-1:0;i<qiqi;i++)
			sum+=a[i];
		cout << sum << endl;
	}
    return 0;
}

上一题