NC14698. 模拟战役
描述
输入描述
第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; }