codeforces 254D Rats(剪枝搜索)

题目链接：http://codeforces.com/problemset/problem/254/D

题意：一个n*m的方格，其中包括：（1）字母X表示障碍；（2）字母R表示老鼠；（3）点号表示空格。现在要在非障碍格子中放置两个炸弹（两个炸弹不能放在同一个格子里），炸掉所有老鼠？已知炸弹的有限范围为d（曼哈顿距离）但是不能通过障碍格子，即炸弹的范围不能穿过障碍格子。

思路：由于d比较小，所以老鼠过多的时候必定炸不完。每个炸弹最多干掉2*d*d+2*d+1个老鼠。这是第一个剪枝。然后从每个老鼠开始，记录可以炸掉该老鼠的格子，并同时记录每个格子覆盖的老鼠个数，这样的格子也没有多少(因为经过第一个剪枝现在总的老鼠个数也没有多少)。然后在这些格子中枚举两个进行BFS判断是否可行。这时由于之前记录了每个格子可以炸掉多少个老鼠，所以枚举时首先判断若两个炸弹覆盖的老鼠个数小于老鼠总个数，必然不行。这是第二个剪枝。

 

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <string>

#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>=0?(x):-(x))
#define i64 long long
#define u32 unsigned int
#define u64 unsigned long long
#define clr(x,y) memset(x,y,sizeof(x))
#define pb(x) push_back(x)
#define SZ(x) x.size()
using namespace std;

const i64 mod=1000000007;
const int MAX=1005;

struct node
{
    int x,y,d;

    node(){}
    node(int _x,int _y)
    {
        x=_x;
        y=_y;
    }
    node(int _x,int _y,int _d)
    {
        x=_x;
        y=_y;
        d=_d;
    }
};

char s[MAX][MAX];
int n,m,d,visit[MAX][MAX];
vector<node> rat,r;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

void Add(int x,int y)
{
    int i;
    node a;
    for(i=0;i<SZ(r);i++)
    {
        a=r[i];
        if(a.x==x&&a.y==y)
        {
            r[i].d++;
            return;
        }
    }
    r.pb(node(x,y,1));
}

int OK(node a,node b)
{
    queue<node> Q;
    int i,x,y;
    clr(visit,0);
    a.d=0;Q.push(a);visit[a.x][a.y]=1;
    b.d=0;Q.push(b);visit[b.x][b.y]=1;
    while(!Q.empty())
    {
        a=Q.front();
        Q.pop();
        for(i=0;i<4;i++)
        {
            x=a.x+dx[i];
            y=a.y+dy[i];
            if(x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]!='X'&&!visit[x][y]&&a.d+1<=d)
            {
                visit[x][y]=1;
                Q.push(node(x,y,a.d+1));
            }
        }
    }
    for(i=0;i<SZ(rat);i++)
    {
        a=rat[i];
        if(!visit[a.x][a.y]) return 0;
    }
    return 1;
}


int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    while(scanf("%d%d%d",&n,&m,&d)!=-1)
    {
        int i,j,k;
        for(i=1;i<=n;i++) scanf("%s",s[i]+1);
        rat.clear();
        for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(s[i][j]=='R')
        {
            rat.pb(node(i,j));
        }
        if(SZ(rat)>2*(2*d*d+2*d+1))
        {
            puts("-1");
            continue;
        }
        r.clear();
        node a,b;
        int x,y;
        for(i=0;i<SZ(rat);i++)
        {
            a=rat[i];
            for(j=-d;j<=d;j++) for(k=-d;k<=d;k++) if(abs(j)+abs(k)<=d)
            {
                x=a.x+j;
                y=a.y+k;
                if(x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]!='X')
                {
                    Add(x,y);
                }
            }
        }
        int flag=0;
        for(i=0;i<SZ(r)&&!flag;i++) for(j=i+1;j<SZ(r)&&!flag;j++)
        {
            if(r[i].d+r[j].d<SZ(rat)) continue;
            if(OK(r[i],r[j])) a=r[i],b=r[j],flag=1;
        }
        if(!flag) puts("-1");
        else
        {
            printf("%d %d %d %d\n",a.x,a.y,b.x,b.y);
        }
    }
    return 0;
}