usaco 2.4.2 Overfencing

1、这道题我被卡了好久。原因就在于输入搞错了。好吧主要还是我基本功不扎实。一下是我改正后的输入部分。

2、int w[i][j]表示i行j列如果是障碍则为0；通道则为1.

int s[i][j]表示到i行j列的最短路径。

比较懒，直接用递归做的。递归分别从两个入口开始。初始化s全部为100000（第一次因为这个数开得太小了就没过）。为了剪枝。如果搜索i，j时走过的路径比原来记录的大的话就剪枝。否则记录。一下是移动方程。

3、还要注意一点。记录的s并不直接是步数。而是（步数+1)/2 !!!!!这个地方我也错了一回。

4、一下是我的代码：

#include<stdio.h>

#include<string.h>

#include<sstream>

#include<string>

#include<iostream>

#define FF for(i=0;i<H;i++) for(j=0;j<W;j++)

using namespace std;

int s[202][80];

int H,W;

int w[202][80];

void move(int i,int j){

if(i-1>0&&w[i-1][j]&&s[i-1][j]>s[i][j]+1){

s[i-1][j]=s[i][j]+1;

move(i-1,j);

}

if(j-1>0&&w[i][j-1]&&s[i][j-1]>s[i][j]+1){

s[i][j-1]=s[i][j]+1;

move(i,j-1);

}

if(i+1<H&&w[i+1][j]&&s[i+1][j]>s[i][j]+1){

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

move(i+1,j);

}

if(j+1<W&&w[i][j+1]&&s[i][j+1]>s[i][j]+1){

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

move(i,j+1);

}

}

int main(){

int ai,aj,bi,bj;

ai=-1;

int i,j,k;

string tmp;

for(i=0;i<202;i++){

for(j=0;j<80;j++)

s[i][j]=100000;

}

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

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

cin>>W>>H;

getchar();

W=W*2+1;

H=H*2+1;

for(i=0;i<H;i++)

{

getline(cin,tmp);

for(j=0;j<W;j++){

if(tmp[j]==' '){

w[i][j]=1;

if(i==0||i==H-1||j==0||j==W-1){

if(ai==-1){

ai=i;

aj=j;

}

else{

bi=i;

bj=j;

}

}

}

else w[i][j]=0;

}

tmp.clear();

}

s[ai][aj]=0;

s[bi][bj]=0;

move(ai,aj);

move(bi,bj);

int max=0;

FF{

if(s[i][j]!=100000&&s[i][j]>max){

max=s[i][j];

}

}

printf("%d\n",(max+1)/2);

return 0;

}