©2020-2024 ioDraw All rights reserved,
Privacy Policy
L1-7 机工士姆斯塔迪奥 (20 分)
在 MMORPG《最终幻想14》的副本“乐欲之所瓯博讷修道院”里，BOSS 机工士姆斯塔迪奥将会接受玩家的挑战。
你需要处理这个副本其中的一个机制：N×M 大小的地图被拆分为了 N×M 个 1×1 的格子，BOSS
会选择若干行或/及若干列释放技能，玩家不能站在释放技能的方格上，否则就会被击中而失败。
给定 BOSS 所有释放技能的行或列信息，请你计算出最后有多少个格子是安全的。
输入格式:
输入第一行是三个整数 N,M,Q (1≤N×M≤10的5次方，0≤Q≤1000)，表示地图为 N 行 M 列大小以及选择的行/列数量。
接下来 Q 行，每行两个数 Ti,Ci，其中 Ti=0 表示 BOSS 选择的是一整行，Ti=1 表示选择的是一整列，Ci
为选择的行号/列号。行和列的编号均从 1 开始。
输出格式:
输出一个数，表示安全格子的数量。
输入样例:
5 5 3 0 2 0 4 1 3
输出样例:
12
代码如下：（PS：分别有巧劲版和暴力版）
巧劲版
思路1：
别去想过程，直接看结果：假设有 n行，m列，然后BOSS一共 攻击了r个不同行和c个不同列，则：
每一行有m个格子，共 r 行被攻击，一共m*r个格子;
每一列有n个格子，共 c 列被攻击，一共n*c个格子;
其中，是不是有r*c个格子是重复计算了的，（想象一下：a条横线和b条竖线是不是有a*b个交点）
举个例子：有100行，88列，被攻击的不同行列有 1行，2列，那就是一共有1*88+2*100-1*2被攻击了的格子，这很容易理解吧，
那题目问的安全的格子，不就是拿总数减去被攻击的数嘛，也就是：m*n-r*m-c*n+r*c
所以：代码如下：
#include<stdio.h> int flagr[100001]={0},flagc[100001]={0}; int main(){ int
n,m,q,Ti,Ci,r=0,c=0; scanf("%d%d%d",&n,&m,&q); while(q--){
scanf("%d%d",&Ti,&Ci); if(Ti==0&&flagr[Ci]||Ti==1&&flagc[Ci])
continue; //如果是之前被攻击的行或者列就直接跳过 if(Ti==0){ r++; flagr[Ci]=1; }
else{ c++; //标记已经被攻击过了 flagc[Ci]=1; } }
printf("%d",m*n-r*m-c*n+r*c); }
暴力版
思路2：
建立一共二维数组，全赋值为1，然后攻击哪行（列）就把那行（列）的值全变成0，最后再统计 1 的个数呗。
#include<stdio.h> int main(){ int n,m,q,i,j,Ti,Ci,sum=0;
scanf("%d%d%d",&n,&m,&q); int aa[n+1][m+1]; for(i=1;i<n+1;i++)
for(j=1;j<m+1;j++) aa[i][j]=1; while(q--){
scanf("%d%d",&Ti,&Ci); if(Ti==0) for(i=1;i<m+1;i++)
aa[Ci][i]=0; else for(i=0;i<n+1;i++)
aa[i][Ci]=0; } for(i=1;i<n+1;i++) for(j=1;j<m+1;j++)
if(aa[i][j]) sum++; printf("%d",sum); }
其实两个代码写出来的速度差不多，第一个需要先计算一下准确性啥的，才敢写，第二个读完题就能直接写，所以最后完成的速度差不多，当然，算法效率上，第一个当然要快点。