L1-7 机工士姆斯塔迪奥 (20 分)，C语言

柔情只为你懂 2023-09-29 12:16 45阅读 0赞

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

输出样例:

代码如下：（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);
    }

其实两个代码写出来的速度差不多，第一个需要先计算一下准确性啥的，才敢写，第二个读完题就能直接写，所以最后完成的速度差不多，当然，算法效率上，第一个当然要快点。