山东省ACM第三届省赛试题

81 阅读 0 评论 54 点赞

我是靠谱客的博主简单嚓茶，最近开发中收集的这篇文章主要介绍山东省ACM第三届省赛试题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

C： The Best Seat in ACM Contest

题目：n*m的方格，每一个格代表一个队伍，初始值是每个队伍的力量值，通过题意中给定的操作，问最后每个队伍的力量值。
对于每一个方格，若它周围方格方格的数值大于它，就加上两者的差；若是值小于它，就减去两者的差。对于每一个方格都是与原始值进行比较，周围方格经过比较改变了数值，不影响它。若方格的某一侧没有值就减去1.
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t;
int n,m;
int arr[21][21];
int maze[21][21];
int sum;
int jisuan(int a,int x,int y) {
int temp = 0;
if(x-1>=0) {
temp++;
sum += (arr[x-1][y] - arr[x][y]);
}
if(y+1<m) {
temp++;
sum += (arr[x][y+1] - arr[x][y]);
}
if(x+1<n) {
temp++;
sum += (arr[x+1][y] - arr[x][y]);
}
if(y-1>=0) {
temp++;
sum += (arr[x][y-1] - arr[x][y]);
}
temp = 4-temp;//看周围有几个没有值的
sum-=temp;//对于某一侧没有值的情况，要从总和中减去1
return sum;
}
int main() {
scanf("%d",&t);
for(int flag = 1;flag <= t;flag ++) {
scanf("%d%d",&n,&m);
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
scanf("%d",&arr[i][j]);
}
}
int max = -100000000;
int x,y;
for(int i = 0;i < n;i++) {
for(int j = 0;j< m;j++) {
sum = 0;
maze[i][j] = jisuan(arr[i][j],i,j);
if(max<maze[i][j]) {
max = maze[i][j];
x=i;
y=j;
}
}
}
printf("Case %d: %d %d %dn",flag,max,x+1,y+1);
memset(arr,0,sizeof(arr));
memset(maze,0,sizeof(maze));
}
return 0;
}

D： Mine Number

题目大意：输入T个测试案例，每个测试案例输入一个n*m型矩阵。每个数字代表：上下左右，以及该点五个方向雷的数目。
这道题类似于扫雷小游戏，当它周围有0时，那么该点一定没有雷，若该点可以放雷的话，那么它的四周以及它本身都要减去1.

由所给矩阵求出地雷分布图。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[25][25];
char maap[25][25];
bool ispos;
int T,n,m;
int dis[5][2]={0,0, 1,0, -1,0, 0,1, 0,-1};
// 判断出界
bool isout(int x,int y)
{
if( x<0 || y<0 || x>=n || y>=m )
return 1;
return 0;
}
//判断五个点是否有小于等于0的位置
bool location(int x,int y)//没有，返回1
{
int tx,ty;
for(int i=0;i<5;i++)
{
tx=x+dis[i][0];
ty=y+dis[i][1];
if(!isout(tx,ty)&& a[tx][ty]<=0)
return false;
}
return true;
}
//若放雷，数字就减小1
void change(int x,int y)
{
int tx,ty;
for(int i=0;i<5;i++)
{
tx=x+dis[i][0];
ty=y+dis[i][1];
if(isout(tx,ty))
continue;
--a[tx][ty];
}
}
//回溯，本不该放雷，但放了，五个点都加1
void c_back(int x,int y)
{
int tx,ty;
for(int i=0;i<5;i++)
{
tx=x+dis[i][0];
ty=y+dis[i][1];
if(isout(tx,ty))
continue;
++a[tx][ty];
}
}
//判断最后一行是否符合条件
bool judge_final()
{
for(int i=0;i<m;i++)
if(a[n-1][i]!=0) return false;
return true;
}
//输出
void print()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cout<<maap[i][j];
cout<<endl;
}
}
void dfs(int x,int y)
{
if(ispos) return;
if(x==n)//到了最后一行
{
if(judge_final() )
{
ispos=1;//已找到了一种输出
print();
}
return;
}
if(y==m) //到了最后一列
{ dfs(x+1,0);return; }
if(x==0)//对第一行进行枚举
{
if(location(x,y))//对于四周以及本身都不是0的点
{
maap[x][y]='*';
change(x,y);//都五个点都减1
dfs(x,y+1);//继续对同一行的下一个元素进行判断
c_back(x,y);//回溯
}
maap[x][y]='.';
dfs(x,y+1);
}
else//对于剩余的行，根据上一行相应位置来判断
{
if(a[x-1][y]==0)//若上一行对应位置为0，这里不能放雷
{
maap[x][y]='.';
dfs(x,y+1);
}
else if(a[x-1][y]==0)//上一行对应位置为1
//如果这里只写else，最后的结果是wrong
{
if(location(x,y))
{
maap[x][y]='*';
change(x,y);
dfs(x,y+1);
c_back(x,y);
}
}
}
}
int main()
{
char c;
while(scanf("%d",&T)!=EOF)
{
for(int k=1;k<=T;k++)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>c;
//scanf("%c",&c);//用scanf没有输出结果
a[i][j]=c-'0';
}
printf("Case %d:n",k);
ispos=0;//
dfs(0,0);//从0，0点开始
}
}
return 0;
}