守卫

守卫

关注
发信
关注(28)粉丝(399)

【Codevs3567】宫廷守卫

Position：

Description

　　从前有一个王国，这个王国的城堡是一个矩形，被分为M×N个方格。一些方格是墙，而另一些是空地。这个王国的国王在城堡里设了一些陷阱，每个陷阱占据一块空地。

　　 一天，国王决定在城堡里布置守卫，他希望安排尽量多的守卫。守卫们都是经过严格训练的，所以一旦他们发现同行或同列中有人的话，他们立即向那人射击。因此，国王希望能够合理地布置守卫，使他们互相之间不能看见，这样他们就不可能互相射击了。守卫们只能被布置在空地上，不能被布置在陷阱或墙上，且一块空地只能布置一个守卫。如果两个守卫在同一行或同一列，并且他们之间没有墙的话，他们就能互相看见。(守卫就像象棋里的车一样)

　　你的任务是写一个程序，根据给定的城堡，计算最多可布置多少个守卫，并设计出布置的方案。

Input

第一行两个整数M和N(1≤M，N≤200)，表示城堡的规模。

接下来M行N列的整数，描述的是城堡的地形。第i行j列的数用ai,j表示。

ai,j=0，表示方格[i,j]是一块空地；

ai,j=1，表示方格[i,j]是一个陷阱；

ai,j=2，表示方格[i,j]是墙。

Output

第一行一个整数K，表示最多可布置K个守卫。

此后K行，每行两个整数xi和yi，描述一个守卫的位置。

（若有多解，请输出字典序最小的那一种）

Sample Input

3 4

2 0 0 0

2 2 2 1

0 1 0 2

Sample Output

2

1 2

3 1

【Codevs3567】宫廷守卫-LMLPHP

HINT

1≤M，N≤200

Search

这个题范围小一点跑暴力还是可以的，拿来练手，当搜索练习题很好，其中有很多优化，剪枝，可以拿到50分。

剪枝

  1. 记录当前搜索到的点(x,y)，放了之后，预处理连续一段不能选的。见Code→lef数组
  2. 如果上面这列填了，那么就不填了。见Code→f数组。
  3. 并且要用down记录(x,y)选了，往下哪一段不能选。见Code→dow数组。
  4. 每扫过一行，看f数组要不要更新。见Code→b数组，并且当前要用d记录。
  5. 对于横着每一段，选择一个，那么搜索顺序呢？sort每个地方选了，下面有多少个不能选，从小到大搜，可以保证下面选的方案更多。见Code→c数组
  6. 没选完一个(x,y)，记录之后有多少个空地还可以选。如果加上还小于当前ans，就可以return了。见Code→MA数组，记录(x,y)x这排y列之后有多少空地(0)。
  7. 搜索当然可以卡时啦。见if(clock()>CLOCKS_PER_SEC*0.963)pri();

Code

// <guards.cpp> - Fri Sep 23 08:09:06 2016

// This file is made by YJinpeng，created by XuYike's black technology automatically.

// Copyright (C) 2016 ChangJun High School, Inc.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <ctime>

#define MOD 1000000007

#define INF 1e9

using namespace std;

typedef long long LL;

const int MAXN=210;

const int MAXM=40010;

inline int max(int &x,int &y) {return x>y?x:y;}

inline int min(int &x,int &y) {return x<y?x:y;}

inline int gi() {

	register int w=0,q=0;register char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')q=1,ch=getchar();

	while(ch>='0'&&ch<='9')w=w*10+ch-'0',ch=getchar();

	return q?-w:w;

}

int ans,n,m;bool f[MAXN];int b[MAXN];

int a[MAXN][MAXN],lef[MAXN][MAXN],dow[MAXN][MAXN],MA[MAXN][MAXN];

struct gg{int x,y;}g[MAXM],as[MAXM];

struct node{

    int p,w;

    bool operator < (node a)const{return w<a.w;}

};

void pri(){

    printf("%d\n",ans);

    for(int i=1;i<=ans;i++)printf("%d %d\n",as[i].x,as[i].y);

    exit(0);

}

inline void work(register int x,register int y,register int nu){

    if(clock()>CLOCKS_PER_SEC*0.963)pri();

    if(x==n&&y>m){

        if(nu>ans){ans=nu;for(int i=1;i<=nu;i++)as[i]=g[i];}

        return;

    }

    if(y>m){

        int d[MAXN];

        for(int i=1;i<=m;i++){if(x==b[i])f[i]=0;d[i]=b[i];}

        work(x+1,1,nu);

        for(int i=1;i<=m;i++){b[i]=d[i];if(x==b[i])f[i]=1;}

        return;

    }

    int k=MA[x][y];

    for(int i=x+1;i<=n;i++)k+=MA[i][1];

    if(nu+k<=ans)return;

    int tot=0;node c[MAXN];

    for(int i=y;i<lef[x][y];i++){

        if(f[i]||a[x][i])continue;

        c[++tot]=(node){i,dow[x][i]};

    }

    if(!tot){work(x,lef[x][y]+1,nu);return;}

    sort(c+1,c+1+tot);

    for(int i=1;i<=tot;i++){

        f[c[i].p]=1,b[c[i].p]=x+c[i].w;

        g[nu+1]=(gg){x,c[i].p};

        work(x,lef[x][y]+1,nu+1);

        f[c[i].p]=(bool)(b[c[i].p]=0);

    }

}

int main()

{

	freopen("guards.in","r",stdin);

	freopen("guards.out","w",stdout);

	n=gi(),m=gi();

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)a[i][j]=gi();

    for(int i=1;i<=n;i++)lef[i][m+1]=m+1;

    for(int i=1;i<=n;i++)

        for(int j=m;j>=1;j--){

            if(a[i][j]==2){lef[i][j]=j;MA[i][j]=MA[i][j+1];continue;}

            lef[i][j]=lef[i][j+1];

            if(a[i][j]==1&&lef[i][j]==j+1){MA[i][j]=MA[i][j+1];continue;}

            MA[i][j]=MA[i][lef[i][j]+1]+1;

        }

    for(int i=1;i<=m;i++)

        for(int j=n;j>=1;j--){

            if(a[j][i]==2){dow[j][i]=0;continue;}

            dow[j][i]=dow[j+1][i]+1;

        }

    memset(f,false,sizeof(f));

    work(1,1,0);pri();

	return 0;

}

Solution

Code

// <guards.cpp> - Fri Sep 23 08:09:06 2016

// This file is made by YJinpeng，created by XuYike's black technology automatically.

// Copyright (C) 2016 ChangJun High School, Inc.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <ctime>

#define MOD 1000000007

#define INF 1e9

using namespace std;

typedef long long LL;

const int MAXN=210;

const int MAXM=40010;

inline int max(int &x,int &y) {return x>y?x:y;}

inline int min(int &x,int &y) {return x<y?x:y;}

inline int gi() {

    register int w=0,q=0;register char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')q=1,ch=getchar();

    while(ch>='0'&&ch<='9')w=w*10+ch-'0',ch=getchar();

    return q?-w:w;

}

int match[MAXM],X[MAXM],Y[MAXM];

int a[MAXN][MAXN],x[MAXN][MAXN],y[MAXN][MAXN];

vector<int>b[MAXM];int f[MAXM],cnt;

inline void add(int u,int v){b[u].push_back(v);}

bool dfs(int x){

    if(f[x]==cnt)return 0;

    int num=b[x].size();f[x]=cnt;

    for(int i=0;i<num;i++){

        int nex=b[x][i];

        if(match[nex]==-1||dfs(match[nex])){

            match[x]=nex;match[nex]=x;/*f[x]=0;*/return 1;

        }

    }//f[x]=0这句害死人，因为下一次又会再次调用dfs

    return 0;

}

int main()

{

    freopen("guards.in","r",stdin);

    freopen("guards.out","w",stdout);

    int n=gi(),m=gi(),t1=-1,t2=-1,ans=0;

    for(int i=1;i<=n;i++)a[i][0]=2;

    for(int i=1;i<=m;i++)a[0][i]=2;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++){

            a[i][j]=gi();

            if(a[i][j-1]==2)++t1,X[t1]=i;

            x[i][j]=t1;

        }

    for(int j=1;j<=m;j++)

        for(int i=1;i<=n;i++){

            if(a[i-1][j]==2)++t2,Y[t2]=j;

            y[i][j]=t2;

        }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++){

            if(a[i][j])continue;

            add(x[i][j],y[i][j]+t1+1);

        }

    memset(f,false,sizeof(f));

    for(int i=0;i<=t1+t2+1;i++)match[i]=-1;

    for(int i=0;i<=t1;i++)

        if(match[i]==-1){

            cnt++;if(dfs(i))++ans;

            //memset(f,0,sizeof(f));这个不好复杂度高

        }

    printf("%d\n",ans);

    for(int i=0;i<=t1;i++)

        if(match[i]!=-1)printf("%d %d\n",X[i],Y[match[i]-t1-1]);

    return 0;

}

Compare

Codevs提交不了（没有SPJ）WA

我在这里发一个pascal的spj

Program Compare;

{ 本程序为A+B的比较程序，本程序仅作为比较程序的样例。 }

var

  Inf, Ouf, Std, Log: String;

procedure GetParams;

begin

  Inf := Paramstr(1); { 标准输入文件 }

  Ouf := Paramstr(2); { 选手输出文件 }

  Std := Paramstr(3); { 标准输出文件 }

  Log := Paramstr(5); { 结果文件 }

end;

procedure WriteLog(Score: integer; Description: String);

{ 将比较结果写入结果文件中，其中Score为选手的得分百分比，Description为注释。 }

begin

  assign(output, Log); rewrite(output);

  //writeln(Score*10, ' ', Description);

  writeln(Score*10);

  close(output);

  Halt;

end;

var

  a:array[1..200,1..200]of longint;

  x,y:array[1..40000]of longint;

  m,n: Longint; { A与B的值 }

  Sum: Longint; { A+B的标准答案 }

  Ans: Longint; { 选手的输出 }

procedure InfRead;

{ 从输入文件中输入A与B的值。 }

var

  i,j:longint;

begin

  {$i-}

  assign(input, Inf); reset(input);

  readln(m,n);

  for i:=1 to m do

     for j:=1 to n do

         read(a[i,j]);

  close(input);

  {$i+}

  if IOResult <> 0 then WriteLog(0, '输入文件错误！');

end;

procedure StdRead;

{ 从标准输出中输入A与B的和 }

begin

  {$i-}

  assign(input, Std); reset(input);

  read(Sum);

  close(input);

  {$i+}

  if IOResult <> 0 then begin

    WriteLog(0, '标准输出文件错误！');

    halt;

  end;

end;

procedure OufRead;

{ 从输出中输入选手的答案 }

var

  i:longint;

begin

  {$i-}

  assign(input, Ouf); reset(input);

  readln(Ans);

  if Ans<Sum then begin writelog(0,'守卫放置不是最优的'); close(input); halt; end;

  for i:=1 to ans do

      begin

         readln(x[i],y[i]);

         a[x[i],y[i]]:=3;

      end;

  close(input);

  {$i+}

  if IOResult <> 0 then WriteLog(0, '输出文件错误!');

  if ans=sum then writelog(1, '正确')

  else writelog(0, '错误');

end;

procedure Check;

{ 比较选手的解与标准答案 }

var

  i,j,k:longint;

begin

    for i:=1 to ans do

       begin

           j:=x[i];k:=y[i];

           if a[j,k]=1 then begin writelog(0,'踩在陷阱上'); halt; end;

           j:=x[i]+1;

           while (a[j,k]<>2)and(j<=n) do

             begin

                 if a[j,k]=3 then begin writelog(0,'有互相攻击的一对士兵'); halt; end;

                 inc(j);

             end;

           j:=x[i]-1;

           while (a[j,k]<>2)and(j>0) do

             begin

                 if a[j,k]=3 then begin writelog(0,'有互相攻击的一对士兵'); halt; end;

                 dec(j);

             end;

           j:=x[i];k:=y[i]+1;

           while (a[j,k]<>2)and(k<=m) do

             begin

                 if a[j,k]=3 then begin  writelog(0,'有互相攻击的一对士兵'); halt; end;

                 inc(k);

             end;

           k:=y[i]-1;

           while (a[j,k]<>2)and(k>0) do

             begin

                 if a[j,k]=3 then begin writelog(0,'有互相攻击的一对士兵'); halt; end;

                 dec(k);

             end;

       end;

    writelog(1,'正确');

end;

begin

  GetParams;

  InfRead;

  StdRead;

  OufRead;

//  Check;

end.
05-11 22:26
Powered by LMLPHP ©2024 守卫 0.058028