Codeforces #380 738B. Spotlights
传送门:http://codeforces.com/contest/738/problem/B
题目翻译
N×M的网格上有一些演员,一盏灯要放在没有演员的方格且灯光朝向上至少有一个演员。求方案数。
题解
每一行,每一列,从结尾往前扫,边扫边统计即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<cstdio> using namespace std; const int Maxn=1000; int n,m; int mp[Maxn+5][Maxn+5]; int Ans=0; inline void calc(int x,int y,int dx,int dy,int rate){ if (!(1<=x && x<=n && 1<=y && y<=m)) return; if (rate>0 && mp[x][y]==0) Ans++; calc(x+dx,y+dy,dx,dy,rate|mp[x][y]); } int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&mp[i][j]); Ans=0; for (int i=1;i<=n;i++){ calc(i,1,0,1,0); calc(i,m,0,-1,0); } for (int i=1;i<=m;i++){ calc(1,i,1,0,0); calc(n,i,-1,0,0); } printf("%d\n",Ans); return 0; } |

原文链接:Codeforces #380 738B. Spotlights
WNJXYKの博客 版权所有,转载请注明出处。
还没有任何评论,你来说两句吧!