PKU演習問メモ(6/26)

No.	問題名	問題の種類および解法	難易度
3103	Cutting a Block	シミュレート	★☆☆☆☆
2734	Queens, Knights and Pawns	シミュレート	★☆☆☆☆

3103 Cutting a Block

問題概要

与えられた直方体を、n個の同じ形の直方体に分割し、それぞれの頂点を出力せよ。

解法

形は問われないので縦にn等分すればよい。

ソースコード

int main()
{
	int x,y,z,n;
	cin>>x>>y>>z>>n;	
	rep(i,n)printf("%.9f %d %d %.9f %d %d\n",x*1.0*i/n,0,0,x*1.0*(i+1)/n,y,z);
	
	return 0;
}

2734 Queens, Knights and Pawns

問題概要

サイズの与えられたチェス板に、クイーン、ナイト、ポーンの駒が与えられた位置に配置されている。
これらのいずれの駒も利いていないマスの総数を求めよ。
ただし、ここではポーンはコマの利きを止める働きのみを持ち、コマを取る能力はないものとする。

チェス板のサイズは高さ、幅がそれぞれ1000以下、それぞれの駒の数は100以下を満たす。

解法

駒を全て配置してから利きのマスを単純に数えて調べていけばよい。
クイーンの利きは他の駒で止まることに注意。
実装量は多目かも。

ソースコード

int DX[]={-1,1,2,2,1,-1,-2,-2},DY[]={-2,-2,-1,1,2,2,1,-1};

int h,w,k,q,p;
int kx[100],ky[100],qx[100],qy[100],px[100],py[100];

int ans=0;
int bd[1000][1000];

int main()
{
	int cs=0;
	while(cin>>h>>w,h)
	{
		rep(i,h)fill_n(bd[i],w,0);
		cin>>q;
		rep(i,q)
		{
			cin>>qy[i]>>qx[i]; qy[i]--,qx[i]--;
			bd[qy[i]][qx[i]]=-1;
		}
		cin>>k;
		rep(i,k)
		{
			cin>>ky[i]>>kx[i]; ky[i]--,kx[i]--;
			bd[ky[i]][kx[i]]=-1;
		}
		cin>>p;
		rep(i,p)
		{
			cin>>py[i]>>px[i]; py[i]--,px[i]--;
			bd[py[i]][px[i]]=-1;
		}
		
		ans=0;
		rep(i,q)
		{
			for(int dy=-1;dy<=1;dy++)for(int dx=-1;dx<=1;dx++)if(dy||dx)
			{
				int y=qy[i]+dy,x=qx[i]+dx;
				while(0<=y&&y<h&&0<=x&&x<w&&bd[y][x]>=0)
				{
					ans+=bd[y][x]?0:1;
					bd[y][x]=1;
					y+=dy,x+=dx;
				}
			}
		}
		rep(i,k)rep(d,8)
		{
			int y=ky[i]+DY[d],x=kx[i]+DX[d];
			if(y<0||x<0||y>=h||x>=w||bd[y][x])continue;
			bd[y][x]=1; ans++;
		}
		cout<<"Board "<<++cs<<" has "<<h*w-ans-q-k-p<<" safe squares."<<endl;
	}
	return 0;
}