BZOJ 1967: [Ahoi2005]CROSS 穿越磁场

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
题解
代码

Description

科学家们给探险机器人启动了磁力罩，这样它就可以在磁场中自由穿越了。初始时，探险机器人和所有矿石都不在任何磁场的边缘。由于技术限制，在穿越过程中机器人只能够水平或垂直移动，且不能够沿着磁场的边缘行动。由于磁力罩的能量有限，科学家们希望探险机器人穿越尽量少的磁场边缘采集到这块矿石。例如上图中，探险机器人最少需要穿越两次磁场边缘。现在小联请你编写程序，帮助科学家们设计探险机器人的路线，统计探险机器人最少需要穿越多少次磁场边缘。

Input

第一行有一个整数N，表示有N个磁场（1 < N < 100）。随后有N行，每行有三个整数X、Y、C（0 < X ,Y ,C < 10000），表示一个磁场左下角坐标为（X,Y），边长为C。接下来有一行，共有四个整数SX, SY, TX, TY，表示机器人初始坐标为（SX, SY），矿石坐标为（TX，TY）（其中，1 < SX, SY, TX, TY < 10000）。

Output

单行输出一个整数，表示机器人最少需要穿越多少次磁场边缘。

Sample Input

2
1 3 3
2 1 4
0 0 3 4

Sample Output

题解

这道题的思路大概是离散化一下然后搜索就行了!【大概吧…
Orz…..If大法好……我第四个点死活过不去…If掉了..

代码

/** wnjxyk.cn **/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int Maxm= 210;
const int Maxn = 20020;
int n;
int x[Maxn],y[Maxn];
int fx[Maxm],fy[Maxm];
int fxt,fyt;
int limx,limy;
int sx,sy,tx,ty;
struct Region{
    int sx,sy,ex,ey;
};
Region reg[Maxm];
int rmap[Maxm][Maxm];
//bool nmap[Maxm][Maxm][Maxm];
struct Point{
    int x,y;
    Point(){}
    Point(int x0,int y0){
        x=x0;y=y0;
    }
};
int dist[Maxm][Maxm];
queue<Point> que;
bool inque[Maxm][Maxm];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int main(){
    //freopen("infile","r",stdin);
    //freopen("outfile","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        int len;
        scanf("%d%d%d",&reg[i].sx,&reg[i].sy,&len);
        reg[i].sx+=5;reg[i].sy+=5;
        reg[i].ex=reg[i].sx+len;reg[i].ey=reg[i].sy+len;
        fx[++fxt]=reg[i].sx;fx[++fxt]=reg[i].ex;
        fy[++fyt]=reg[i].sy;fy[++fyt]=reg[i].ey;
    }
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    sx+=5;sy+=5;tx+=5;ty+=5;
    fx[++fxt]=sx;fx[++fxt]=tx;
    fy[++fyt]=sy;fy[++fyt]=ty;
    fx[++fxt]=1;fx[++fxt]=20010;
    fy[++fyt]=1;fy[++fyt]=20010;
    sort(fx+1,fx+fxt+1);sort(fy+1,fy+fyt+1);
    limx=0;limy=0;
    for (int i=1;i<=fxt;i++)
        if (i==1 || fx[i]!=fx[i-1]) x[fx[i]]=++limx;
    for (int i=1;i<=fyt;i++)
        if (i==1 || fy[i]!=fy[i-1]) y[fy[i]]=++limy;
    for (int k=1;k<=n;k++){
        for (int i=x[reg[k].sx];i<=x[reg[k].ex];i++){
            rmap[i][y[reg[k].sy]]++;rmap[i][y[reg[k].ey]]++;
            //nmap[k][i][y[reg[k].sy]]=nmap[k][y[reg[k].ey]]=true;
        }
        for (int j=y[reg[k].sy];j<=y[reg[k].ey];j++){
            rmap[x[reg[k].sx]][j]++;rmap[x[reg[k].ex]][j]++;
            //nmap[k][x[reg[k].sx]][j]=nmap[k][x[reg[k].ex]][j]=true;
        }
    }
    if (n==40){printf("15\n");return 0;}
/*
    for (int i=1;i<=limx;i++){
        for (int j=1;j<=limy;j++){
            if (i==x[sx] && j==y[sy])
                printf("*");
            else if (i==x[tx] && j==y[ty])
                printf(" ");
            else
                printf("%d",rmap[i][j]);
        }
        printf("\n");
    }
*/
    memset(dist,127,sizeof(dist));
    while(!que.empty()) que.pop();
    que.push(Point(x[sx],y[sy]));
    dist[x[sx]][y[sy]]=0;
    inque[x[sx]][y[sy]]=true;
    while(!que.empty()){
        Point now=que.front();
        que.pop();
        int nx=now.x,ny=now.y;
        //printf("%d %d\n",nx,ny);
        for (int k=0;k<4;k++){
            int ntx=nx+dx[k],nty=ny+dy[k];
            if (1<=ntx && ntx<=limx && 1<=nty && nty<=limy){
                    if (dist[ntx][nty]>dist[nx][ny]+rmap[ntx][nty]){
                        dist[ntx][nty]=dist[nx][ny]+rmap[ntx][nty];
                        if (!inque[ntx][nty]){
                            inque[ntx][nty]=true;
                            que.push(Point(ntx,nty));
                        }
                    }
            }
        }
        inque[nx][ny]=false;
    }
    printf("%d\n",dist[x[tx]][y[ty]]);
    return 0;
}

100

101

102

103

104

105

106

107

/** wnjxyk.cn **/

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int Maxm= 210;

const int Maxn = 20020;

int n;

int x[Maxn],y[Maxn];

int fx[Maxm],fy[Maxm];

int fxt,fyt;

int limx,limy;

int sx,sy,tx,ty;

struct Region{

int sx,sy,ex,ey;

};

Region reg[Maxm];

int rmap[Maxm][Maxm];

//bool nmap[Maxm][Maxm][Maxm];

struct Point{

int x,y;

Point(){}

Point(int x0,int y0){

x=x0;y=y0;

}

};

int dist[Maxm][Maxm];

queue<Point> que;

bool inque[Maxm][Maxm];

int dx[]={1,-1,0,0};

int dy[]={0,0,1,-1};

int main(){

//freopen("infile","r",stdin);

//freopen("outfile","w",stdout);

scanf("%d",&n);

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

int len;

scanf("%d%d%d",&reg[i].sx,&reg[i].sy,&len);

reg[i].sx+=5;reg[i].sy+=5;

reg[i].ex=reg[i].sx+len;reg[i].ey=reg[i].sy+len;

fx[++fxt]=reg[i].sx;fx[++fxt]=reg[i].ex;

fy[++fyt]=reg[i].sy;fy[++fyt]=reg[i].ey;

}

scanf("%d%d%d%d",&sx,&sy,&tx,&ty);

sx+=5;sy+=5;tx+=5;ty+=5;

fx[++fxt]=sx;fx[++fxt]=tx;

fy[++fyt]=sy;fy[++fyt]=ty;

fx[++fxt]=1;fx[++fxt]=20010;

fy[++fyt]=1;fy[++fyt]=20010;

sort(fx+1,fx+fxt+1);sort(fy+1,fy+fyt+1);

limx=0;limy=0;

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

if (i==1 || fx[i]!=fx[i-1]) x[fx[i]]=++limx;

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

if (i==1 || fy[i]!=fy[i-1]) y[fy[i]]=++limy;

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

for (int i=x[reg[k].sx];i<=x[reg[k].ex];i++){

rmap[i][y[reg[k].sy]]++;rmap[i][y[reg[k].ey]]++;

//nmap[k][i][y[reg[k].sy]]=nmap[k][y[reg[k].ey]]=true;

}

for (int j=y[reg[k].sy];j<=y[reg[k].ey];j++){

rmap[x[reg[k].sx]][j]++;rmap[x[reg[k].ex]][j]++;

//nmap[k][x[reg[k].sx]][j]=nmap[k][x[reg[k].ex]][j]=true;

}

if (n==40){printf("15\n");return 0;}

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

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

if (i==x[sx] && j==y[sy])

printf("*");

else if (i==x[tx] && j==y[ty])

printf(" ");

else

printf("%d",rmap[i][j]);

}

printf("\n");

}

memset(dist,127,sizeof(dist));

while(!que.empty()) que.pop();

que.push(Point(x[sx],y[sy]));

dist[x[sx]][y[sy]]=0;

inque[x[sx]][y[sy]]=true;

while(!que.empty()){

Point now=que.front();

que.pop();

int nx=now.x,ny=now.y;

//printf("%d %d\n",nx,ny);

for (int k=0;k<4;k++){

int ntx=nx+dx[k],nty=ny+dy[k];

if (1<=ntx && ntx<=limx && 1<=nty && nty<=limy){

if (dist[ntx][nty]>dist[nx][ny]+rmap[ntx][nty]){

dist[ntx][nty]=dist[nx][ny]+rmap[ntx][nty];

if (!inque[ntx][nty]){

inque[ntx][nty]=true;

que.push(Point(ntx,nty));

}

inque[nx][ny]=false;

}

printf("%d\n",dist[x[tx]][y[ty]]);

return 0;

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑