Home > Old Blog Posts > USACO 2.4.2 Overfencing

USACO 2.4.2 Overfencing


比castle的算法容易,但比castle的输入更加猥琐。

代码:

/*
ID: dementr1
PROG: maze1
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ofstream fout(“maze1.out”);
int a[3000][80]={},step[3000][80]={},H,W;
int startx[2],starty[2];
int move1[4][2]={{2,0},{-2,0},{0,2},{0,-2}},move2[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int xmax,ymax;
struct pix
{
int x,y;
} list[300000];
void init()
{
int i,j,counter=0,s=0;
char tmp;
FILE *fp=fopen(“maze1.in”,”r”);
fscanf(fp,”%d”,&W);
fscanf(fp,”%d”,&H);
xmax=W*2+1;
ymax=H*2+1;
while(fscanf(fp,”%c”,&tmp)!=EOF)
{
if(tmp==’\n’) continue;
i=counter/(xmax);
j=counter%(xmax);
if(tmp==’ ‘) a[i][j]=0;
else a[i][j]=1;
step[i][j]=-1;

if((j==0||j==W*2||i==0||i==H*2)&&tmp==’ ‘)
{
startx[s]=i;
starty[s]=j;
s++;
step[i][j]=0;
}
counter++;
}
}
void bfs()
{
int open,closed,px,py,i,j;
open=1;
closed=-1;
list[0].x=startx[0];
list[0].y=starty[0];
list[1].x=startx[1];
list[1].y=starty[1];
while(closed<open)
{
closed++;
if(closed<=1)
{
for(i=0;i<4;i++)
{
px=list[closed].x+move2[i][0];
py=list[closed].y+move2[i][1];
if(0<=px&&px<=ymax
&&0<=py&&py<=xmax
&&a[px][py]==0&&(step[px][py]>step[list[closed].x][list[closed].y]+1||step[px][py]==-1))
{
open++;
list[open].x=px;
list[open].y=py;
step[px][py]=step[list[closed].x][list[closed].y]+1;
}
}
}
else
{
for(i=0;i<4;i++)
{
px=list[closed].x+move1[i][0];
py=list[closed].y+move1[i][1];
if(0<=px&&px<=ymax
&&0<=py&&py<=xmax
&&a[px-move2[i][0]][py-move2[i][1]]==0&&(step[px][py]>step[list[closed].x][list[closed].y]+1||step[px][py]==-1))
{
open++;
list[open].x=px;
list[open].y=py;
step[px][py]=step[list[closed].x][list[closed].y]+1;
}
}
}
}
int max=-1;
for(i=0;i<ymax;i++)
for(j=0;j<xmax;j++)
if(step[i][j]>max) max=step[i][j];
fout<<max<<endl;
}
int main()
{
init();
bfs();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: