poj 1101

//======================================

这道题大多数人都用的是广搜+优先队列，不过我的做法是深搜

做起来还不是很繁琐，不过最让人诧异的就是我原来把数组开到了

77 ，因为w,h最大值是75加上两行外围空地，最大开到77就可以了啊

但是结果却是一直WA，困扰我很长时间，后来改到数组开到了100

ok ac.，觉得很怪异，然后把数组开到78还是可以ac的，发出来

供路过的acmer指点迷津。。。

//======================================

#include <iostream>
#include <string>
#define MAXN 78
#define min _min
#define inf 123456789
using namespace std;

char _m[MAXN][MAXN];
bool mark[MAXN][MAXN];
int dp[MAXN][MAXN];
int dis[4][2] = {0,1,0,-1,1,0,-1,0};
int dis_mark[4] = {4,3,2,1};
int min;
int x_2;
int y_2;
int real_w;
int real_h;
void dfs(int x,int y,int dir,int step);
int main()
{
freopen("acm.acm","r",stdin);
// freopen("out.txt","w",stdout);
int w;
int h;
int i;
int j;
int x_1;
int y_1;
int temp_x;
int temp_y;
string s;
int time = 0;
while(cin>>w>>h,w||h)
{
   cout<<"Board #"<<++ time<<":"<<endl;
   getchar();
   int time_in = 0;
   real_w = w+2;
   real_h = h+2;
   memset(_m,' ',sizeof(_m));
   for(i = 1; i <= h; ++ i)
   {
    getline(cin,s);
    for(j = 1; j <= w; ++ j)
    {
     _m[i][j] = s[j-1];
    }
   }

  
   while(cin>>y_1>>x_1>>y_2>>x_2,x_1||y_1||x_2||y_2)
   {
   
    cout<<"Pair "<<++ time_in<<": ";
    memset(mark,false,sizeof(mark));
    for(i = 0; i < MAXN; ++ i)
    {
     for(j = 0; j < MAXN; ++ j)
     {
      dp[i][j] = inf;
     }
    }
    min = inf;
    for(i = 0; i < 4; ++ i)
    {
     temp_x = x_1 + dis[i][0];
     temp_y = y_1 + dis[i][1];
     if((_m[temp_x][temp_y] != 'X' ||_m[temp_x][temp_y] == 'X' && temp_x == x_2 && temp_y == y_2) && !mark[temp_x][temp_y])
     {
      mark[temp_x][temp_y] = true;
      dfs(temp_x,temp_y,dis_mark[i],1);
   
      mark[temp_x][temp_y] = false;
     }
    }
    if(min == inf)
    {
     cout<<"impossible."<<endl;
    }
    else
    {
     cout<<min;
     cout<<" segments."<<endl;
    }
   }
   cout<<endl;
}
}

void dfs(int x,int y,int dir,int step)
{
if(x == x_2 && y == y_2)
{
   if(step < min)
   {
    min = step;
   }
   return;
}

if(step < dp[x][y])
{
   dp[x][y] = step;
}
else
{
   return;
}

int i;
int j;
int temp_x;
int temp_y;// 右
for(i = 0; i < 4; ++ i)
{
   temp_x = dis[i][0] + x;
   temp_y = dis[i][1] + y;
   if(temp_x >= 0 && temp_x < real_h && temp_y >= 0 && temp_y <= real_w &&( _m[temp_x][temp_y] != 'X' || _m[temp_x][temp_y] == 'X' && temp_x == x_2 && temp_y == y_2)&& !mark[temp_x][temp_y])
   {
    mark[temp_x][temp_y] = true;
    if(dis_mark[i] != dir)
    {
     dfs(temp_x,temp_y,dis_mark[i],step+1);
     if(step+1 < dp[temp_x][temp_y])
      dp[temp_x][temp_y] = step+1;
    }
    else
    {
     dfs(temp_x,temp_y,dis_mark[i],step);
     if(step < dp[temp_x][temp_y])
      dp[temp_x][temp_y] = step;
    }
    mark[temp_x][temp_y] = false;
   }
}

}

posted on 2010-06-19 17:00 成大才子 阅读(692) 评论(2)  编辑 收藏 引用

评论

# re: poj 1101 2010-09-14 15:43 rayafjyblue

数组开78大概是因为字符串数组的每一行都有个‘\0’吧,所以要大一点。。。。。偶也是菜鸟。。。。  回复  更多评论   

# re: poj 1101 2010-09-25 09:08 caizi

@rayafjyblue
呵呵，好像不是那个原因。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年9月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

公告

关于更多关于成大才子，请访问http://hi.baidu.com/成大才子

常用链接

留言簿(1)

随笔档案

文章分类

文章档案

链接

搜索

最新评论

阅读排行榜

评论排行榜