hdu 5254 棋盘占领（百度之星2015初赛2 1003）暴力模拟

本文主要是介绍hdu 5254 棋盘占领（百度之星2015初赛2 1003）暴力模拟，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1001


11

11

4
2 2
2
1 1
2 2
3 3
3
1 1
2 3
3 2
2 4
5
1 1
1 1
1 2
1 3
1 4
2 4
2
1 1
2 4

Case #1:
4
Case #2:
9
Case #3:
4
Case #4:
2

我暴力过掉了。

枚举每个未被占领的城市在当前是否会被占领。

用vector保存了未被占领的城市。

代码如下：

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<int>vx;
vector<int>vy;
int n,m;
int a[555][555];
bool judge(int x,int y)
{int tem1 = 0;int tem2 = 0;int tem3 = 0;int tem4 = 0;if(x>1&&a[x-1][y]==1)tem1++;if(x<n&&a[x+1][y]==1)tem2++;if(y>1&&a[x][y-1])tem3++;if(y<m&&a[x][y+1])tem4++;return ((tem1&tem3)|(tem1&tem4)|(tem2&tem3)|(tem2&tem4));
}
int main()
{int T,i,j,k,q,ca=1,x,y;scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&q);memset(a,0,sizeof(a));for(i=0; i<q; i++){scanf("%d%d",&x,&y);a[x][y]=1;}vx.clear();vy.clear();for(i=1; i<=n; i++){for(j=1; j<=m; j++){if(a[i][j]==0){vx.push_back(i);vy.push_back(j);}}}bool flag = false;while(!flag){flag = true;for(i=0; i<vx.size(); i++){x = vx[i];y = vy[i];if(judge(x,y)){flag = false;a[x][y]=1;vx.erase(vx.begin()+i);vy.erase(vy.begin()+i);i--;}}}printf("Case #%d:\n",ca++);printf("%d\n",(n*m-vx.size()));}return 0;
}

这篇关于hdu 5254 棋盘占领（百度之星2015初赛2 1003）暴力模拟的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！