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

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

評論

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

數組開78大概是因為字符串數組的每一行都有個‘\0’吧,所以要大一點。。。。。偶也是菜鳥。。。。  回復  更多評論   

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

@rayafjyblue
呵呵,好像不是那個原因。  回復  更多評論   


只有注冊用戶登錄后才能發表評論。
網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


<2010年6月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

導航

統計

公告

關于更多關于成大才子,請訪問http://hi.baidu.com/成大才子

常用鏈接

留言簿(1)

隨筆檔案

文章分類

文章檔案

鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产精品嫩草久久久久| 黄网站色欧美视频| 亚洲影院色在线观看免费| 亚洲精品黄色| 欧美日韩在线一二三| 亚洲一区精品视频| 亚洲一区二区网站| 国内成+人亚洲+欧美+综合在线| 久久av一区| 老司机精品导航| 日韩视频亚洲视频| 亚洲一区欧美二区| 激情丁香综合| 亚洲精品国产精品国自产观看| 欧美视频国产精品| 久久久噜噜噜久久久| 久久久久久一区| 日韩午夜在线视频| 亚洲欧美www| 亚洲激情影院| 亚洲综合色婷婷| 亚洲激情在线播放| 一区二区三区不卡视频在线观看 | 欧美69wwwcom| 欧美精品一区在线发布| 欧美一区二区三区四区在线观看地址 | 亚洲盗摄视频| 国产精品国产a级| 欧美1区视频| 国产精品嫩草久久久久| 美国十次成人| 国产精品成人一区二区三区吃奶| 久久免费精品视频| 欧美三级免费| 欧美黄网免费在线观看| 国产美女精品视频免费观看| 亚洲电影视频在线| 国产一区视频在线看| 日韩亚洲精品在线| 亚洲第一久久影院| 午夜欧美电影在线观看| 99国产精品视频免费观看| 欧美中文字幕视频| 亚洲欧美视频一区二区三区| 欧美va亚洲va香蕉在线| 久久婷婷久久| 国产欧美精品日韩| 在线亚洲激情| 一本色道久久88综合日韩精品| 久久精品91久久香蕉加勒比| 亚洲欧美日韩精品综合在线观看| 乱码第一页成人| 久久中文久久字幕| 国产三级欧美三级日产三级99| 99国产精品久久久| 亚洲免费精品| 欧美福利在线| 亚洲国产精品t66y| 亚洲国产一区二区三区青草影视| 久久福利影视| 久久青草欧美一区二区三区| 国产视频在线观看一区 | 欧美成熟视频| 亚洲国产一区视频| 欧美xxx成人| 亚洲高清在线观看一区| 亚洲国产精品成人久久综合一区| 久久亚洲国产精品日日av夜夜| 午夜精品电影| 国产区二精品视| 小黄鸭精品aⅴ导航网站入口| 欧美一区二区三区久久精品茉莉花| 欧美性猛交视频| 这里只有精品电影| 欧美一区二区三区在线视频| 国产精品一区免费观看| 亚洲综合日韩| 久久免费高清| 91久久久在线| 欧美三级精品| 小嫩嫩精品导航| 欧美成人精品h版在线观看| 亚洲国产第一| 欧美日韩在线看| 亚洲欧美日本另类| 蜜桃av一区| 日韩视频永久免费| 国产精品视频成人| 欧美一区日本一区韩国一区| 欧美成人激情在线| 亚洲视频欧美视频| 国产欧美日韩一区二区三区在线| 久久精品亚洲国产奇米99| 欧美韩日视频| 午夜精品国产更新| 伊人精品成人久久综合软件| 欧美高清视频在线| 午夜欧美精品久久久久久久| 欧美粗暴jizz性欧美20| 亚洲一区免费在线观看| 狠狠色2019综合网| 欧美色精品天天在线观看视频| 午夜精品免费视频| 亚洲人久久久| 久久精品视频导航| 夜夜精品视频一区二区| 国产一区二区三区在线免费观看 | 国产日韩一区二区三区在线| 久热精品视频在线| 亚洲欧美综合一区| 亚洲激情一区| 久久人人九九| 亚洲一区国产一区| 亚洲大胆女人| 国产欧美一区二区三区沐欲| 欧美国产日韩一区| 久久久久久噜噜噜久久久精品| 亚洲伦理自拍| 欧美www视频| 久久精选视频| 亚洲欧美另类综合偷拍| 亚洲国产综合91精品麻豆| 国产欧美日本在线| 欧美三级电影一区| 欧美激情在线狂野欧美精品| 欧美一级视频一区二区| 一区二区三区国产在线| 亚洲国产欧美一区二区三区同亚洲| 久久精品视频导航| 欧美在线视频观看免费网站| 亚洲一区二区av电影| 亚洲激情二区| 亚洲国产精品va| 影音国产精品| 一区二区亚洲精品| 国产午夜精品久久久久久免费视| 欧美日韩国产一中文字不卡| 欧美电影免费观看| 看片网站欧美日韩| 久久综合精品一区| 久久米奇亚洲| 久久亚洲午夜电影| 久久综合九色欧美综合狠狠| 久久人人97超碰精品888| 欧美自拍偷拍午夜视频| 午夜精彩国产免费不卡不顿大片| 亚洲视频一区二区| 亚洲男人第一网站| 亚洲综合色自拍一区| 午夜精彩国产免费不卡不顿大片| 亚洲影视九九影院在线观看| 亚洲综合欧美日韩| 欧美与黑人午夜性猛交久久久| 欧美一级二区| 久久久精品一区二区三区| 久久久国产视频91| 美国成人直播| 欧美日韩国产免费观看| 欧美日韩国产精品一卡| 欧美午夜剧场| 国产日韩在线视频| 亚洲成人在线视频播放| 亚洲精品国产精品国自产在线 | 免费成人av| 欧美激情一二区| 亚洲麻豆av| 午夜在线不卡| 免播放器亚洲一区| 欧美天天综合网| 国产亚洲激情在线| 亚洲国产欧美国产综合一区| aa级大片欧美| 欧美制服丝袜| 欧美高清在线一区| 99精品视频免费| 久久国产精品99精品国产| 欧美国产亚洲另类动漫| 欧美性色视频在线| 激情五月***国产精品| 日韩一区二区免费高清| 欧美一区二区久久久| 欧美国产综合视频| 亚洲一区二区在线观看视频| 麻豆亚洲精品| 国产欧美日本一区二区三区| 亚洲国产精品一区二区久| 亚洲尤物在线视频观看| 久久久噜噜噜| 亚洲视频自拍偷拍| 欧美成人精品1314www| 国产精品一区亚洲| 亚洲精品欧美日韩| 久久久久久久综合色一本| 亚洲精品一区二区三区婷婷月 | 欧美日韩成人综合在线一区二区| 国产日韩一区| 亚洲免费视频观看| 欧美成人午夜免费视在线看片| 亚洲一区二区三| 欧美日韩不卡在线|