计蒜客第四场 A（搜索）

本文主要是介绍计蒜客第四场 A（搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

商汤科技致力于引领人工智能核心“深度学习”技术突破，构建人工智能、大数据分析行业解决方案。作为一家人工智能公司，用机器自动地解决各类实际问题自然不在话下。近日，商汤科技推出了一套安全令牌，令牌如下图所示：

安全令牌上的小孔有 $n$ 行 $m$ 列，不过有些行和有些列已经用导线整体焊接了，共有 $k$ 根导线。

我们可以在安全令牌上不重叠地焊接若干个小芯片，每个芯片需要在相邻（不能斜着相邻，必须平行于行或列）的两个没有被焊接的小孔上固定。不能固定在已经被整体焊接的行或列上。

安全令牌上最多可以放置多少个芯片，就代表了这个安全令牌对应的校验码。当然，由于安全令牌上小孔的密度会很大，是很难目测出对应的校验码的。你作为商汤科技的实习生，需要写出一个程序，能够自动地算出一个给定的安全令牌的校验码。

输入格式

输入第一行三个整数 $\le n,m \le 100)$ ， $\le k \le n + m)$ 。

接下来输入 $k$ 行，每行输入两个整数 $\le d \le 1)$ ， $c$ 。如果 $d = 0$ ，表示第 $\le c \le n)$ 行被整体焊接了，如果 $d = 1$ ，表示第 $\le c \le m)$ 列被整体焊接了。

输出格式

输出安全令牌对应的校验码。

样例输入

4 5 2
0 3
1 4

样例输出

思路：

用搜索即可！！

代码：

#include <bits/stdc++.h>
using namespace std;
const int M=102;
bool g[M][M];
int n,m;
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int calu()
{int res=0;for(int i=1;i<=n;++i){for(int j=1;j<=m;j++){if(g[i][j])continue;for(int k=0;k<4;k++){int xx=i+dx[k];int yy=j+dy[k];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!g[xx][yy]){g[xx][yy]=true;res++;}}}
}
return res;
}
int main()
{int k,a,b;while(cin>>n>>m>>k){memset(g,0,sizeof(g));while(k--){cin>>a>>b;if(a==0){for(int i=1;i<=m;i++)g[b][i]=true;}if(a==1){for(int i=1;i<=n;i++){g[i][b]=true;}}}cout<<calu()<<endl;}return 0;
}

这篇关于计蒜客第四场 A（搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！