亚洲国产你懂的,欧美极品在线播放,国产主播在线一区

Microsoft.Cpp.Chengdacaizi

天行健，君子以自強(qiáng)不息地勢(shì)坤，君子以厚德載物

poj 1101

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

這道題大多數(shù)人都用的是廣搜+優(yōu)先隊(duì)列，不過(guò)我的做法是深搜

做起來(lái)還不是很繁瑣，不過(guò)最讓人詫異的就是我原來(lái)把數(shù)組開到了

77 ，因?yàn)閣,h最大值是75加上兩行外圍空地，最大開到77就可以了啊

但是結(jié)果卻是一直WA，困擾我很長(zhǎng)時(shí)間，后來(lái)改到數(shù)組開到了100

ok ac

.，覺得很怪異，然后把數(shù)組開到78還是可以ac的，發(fā)出來(lái)

供路過(guò)的acmer指點(diǎn)迷津。。。

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

#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 成大才子閱讀(715) 評(píng)論(2) 編輯收藏引用

評(píng)論

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

數(shù)組開78大概是因?yàn)樽址當(dāng)?shù)組的每一行都有個(gè)‘\0’吧,所以要大一點(diǎn)。。。。。偶也是菜鳥。。。。回復(fù) 更多評(píng)論

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

@rayafjyblue
呵呵，好像不是那個(gè)原因。回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

<

2010年6月

>

日

一

二

三

四

五

六

30

31

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

1

2

3

4

5

6

7

8

9

10

導(dǎo)航

統(tǒng)計(jì)

隨筆 - 16
文章 - 1
評(píng)論 - 4
引用 - 0

公告

關(guān)于更多關(guān)于成大才子，請(qǐng)?jiān)L問(wèn)http://hi.baidu.com/成大才子

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

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

poj 1101

評(píng)論

導(dǎo)航

統(tǒng)計(jì)

公告

常用鏈接

留言簿(1)

隨筆檔案

文章分類

文章檔案

鏈接

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜