LightOJ - 1010 Knights in Chessboard(规律)

题目链接：https://vjudge.net/contest/28079#problem/B

题目大意：给你一个nxm的棋盘，问你最多可以放几个骑士让他们互相攻击不到。骑士攻击方式如下图：

解题思路：当m和n都大于2时，ans=（m*n+1）/2

　　　　　当m或n有一个为1时，ans=m*n

　　　　　当m或n有一个为2时，那么我们可以考虑可以分出多少个2*2的格子(t田字格) ,那么我们可以一次把一个田字格全部放上马，然后间隔一个田字格，然后再放马，使m=max(n,m),判断田字格两两匹配后剩下的格子数tmp=m-m/4*4，若tmp>=2,ans=(m/4+1)*4,否则ans=m/4*4+tmp*2;

代码：

 #include<iostream>

 #include<stdio.h>

 #include<algorithm>

 using namespace std;

 int main(){

     int t,m,n;

     scanf("%d",&t);

     for(int i=;i<=t;i++){

         int ans;

         scanf("%d%d",&m,&n);

         if(m>&&n>)

             ans=(m*n+)/;

         if(m==||n==){

             ans=m*n;

         }

         else if(m==||n==){

             if(m<n)

                 swap(m,n);

             ans=m/*;

             //匹配了成对田字格后剩下的格子

             int tmp=m-m/*;

             if(m%>=)

                 ans+=;

             else

                 ans+=m%*;

         }

         printf("Case %d: %d\n",i,ans);

     }

 }

巴特西

LightOJ - 1010 Knights in Chessboard(规律)

最新文章

热门文章