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

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

評論

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

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

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

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

<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

導航

統計

公告

關于更多關于成大才子,請訪問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>
            亚洲国产精品第一区二区| 韩国成人理伦片免费播放| 玖玖玖国产精品| 国产乱肥老妇国产一区二| 99热在线精品观看| 久久久久亚洲综合| 久久国产手机看片| 国产主播精品| 免费亚洲一区| 欧美屁股在线| 午夜精品偷拍| 久久久精品2019中文字幕神马| 国产欧美另类| 欧美一区中文字幕| 久久精品视频99| 亚洲第一综合天堂另类专| 欧美成人精品一区| 欧美精品一卡| 欧美专区在线| 欧美国产综合视频| 久久精品综合| 欧美风情在线观看| 亚洲一区二区三区四区视频| 在线一区二区三区做爰视频网站| 欧美日韩无遮挡| 欧美亚洲免费高清在线观看| 久久久久天天天天| 香蕉成人久久| 在线观看日韩| 亚洲精选大片| 亚洲大黄网站| 性久久久久久久| 91久久久久久久久| 性欧美大战久久久久久久免费观看| 国产精品尤物| 亚洲国产小视频在线观看| 国产精品美女黄网| 亚洲人成网站在线播| 欧美高清视频在线观看| 亚洲综合视频在线| 国产情侣一区| 久久久久这里只有精品| 欧美大片一区二区| 亚洲深夜福利视频| 欧美激情精品久久久| 亚洲电影在线播放| 亚洲字幕一区二区| 国产美女精品人人做人人爽| 亚洲免费视频观看| 欧美aⅴ一区二区三区视频| 亚洲毛片在线| 国产精品女人网站| 欧美在线国产| 亚洲第一主播视频| 午夜精品一区二区三区四区| 国产亚洲制服色| 欧美成人精品激情在线观看| 日韩一级黄色av| 暖暖成人免费视频| 亚洲欧美日韩国产中文| 亚洲人成网站色ww在线| 国产精品videosex极品| 久久国产视频网站| 韩国女主播一区二区三区| 久久综合福利| 亚洲一区二区三区乱码aⅴ蜜桃女| 国产精品美女www爽爽爽| 欧美久久久久久久久| 牛牛精品成人免费视频| 欧美一区二视频在线免费观看| 99国产精品久久久久老师| 嫩草影视亚洲| 久久亚洲欧美| 国产一区二区丝袜高跟鞋图片| 在线视频精品一区| 日韩午夜电影在线观看| 开心色5月久久精品| 免费成人美女女| 一区二区高清在线| 亚洲精品美女在线观看| 亚洲第一在线| 亚洲激情视频在线播放| 亚洲国产成人午夜在线一区| 日韩亚洲欧美成人一区| 亚洲香蕉网站| 久久亚洲二区| 日韩一二三区视频| 欧美自拍丝袜亚洲| 欧美a级片网站| 国产精品亚洲欧美| 久久久99爱| 亚洲激情一区二区| 久久精品一本| 影音先锋国产精品| 久久午夜电影网| 久久riav二区三区| 国内久久婷婷综合| 香蕉久久a毛片| 亚洲人久久久| 久久国产88| 国产欧美日韩伦理| 亚洲精品欧美日韩专区| 久久久久国内| 久久国产精品第一页| 亚洲国产精品黑人久久久| 亚洲黄色av一区| 亚洲在线免费| 一本色道久久综合狠狠躁的推荐| 午夜天堂精品久久久久| 免费欧美在线| 韩国欧美一区| 亚洲大胆在线| 亚洲激情第一页| 女人香蕉久久**毛片精品| 久久精品国产第一区二区三区| 在线观看日韩专区| 国产亚洲一区二区在线观看| 一区二区久久久久久| 老司机精品视频网站| 99综合在线| 日韩系列欧美系列| 亚洲一区二区av电影| 欧美第一黄网免费网站| 国产欧美视频一区二区| 亚洲影音先锋| 日韩视频永久免费观看| 亚洲成人在线免费| 激情欧美日韩一区| 国产精品成人免费| 亚洲国内自拍| 欧美成人资源| 欧美视频中文字幕在线| 性18欧美另类| 久久精品国产欧美亚洲人人爽| 亚洲国产精品成人久久综合一区| 亚洲第一二三四五区| 欧美色大人视频| 欧美bbbxxxxx| 国产精品爱啪在线线免费观看| 欧美在线综合视频| 欧美激情一级片一区二区| 久久久噜噜噜久久中文字免| 欧美成人影音| 亚洲电影在线看| 1024成人| 欧美mv日韩mv亚洲| 亚洲国产日韩欧美综合久久| 狠狠久久五月精品中文字幕| 久久高清免费观看| 国产三区二区一区久久| 久久精品官网| 免费看av成人| 在线一区二区视频| 亚洲午夜精品在线| 国产一区二区精品久久91| 欧美大片va欧美在线播放| 亚洲一区视频在线| 亚洲大片一区二区三区| 欧美日韩一区精品| 美女网站在线免费欧美精品| 午夜精品久久久久久久99水蜜桃| 亚洲国内在线| 久久综合狠狠综合久久综合88| 亚洲欧美综合| 亚洲视频免费看| 亚洲欧洲一区二区天堂久久| 国产一区二区三区久久| 国产精品欧美在线| 欧美日韩高清在线观看| 欧美成人免费在线| 久久在线免费视频| 欧美一区二区成人6969| 亚洲视频第一页| 在线视频一区二区| 艳妇臀荡乳欲伦亚洲一区| 亚洲激情在线播放| 免费观看久久久4p| 麻豆九一精品爱看视频在线观看免费| 欧美亚洲视频| 小黄鸭精品aⅴ导航网站入口| 亚洲一区国产| 午夜精品免费| 欧美在线免费播放| 午夜视黄欧洲亚洲| 午夜亚洲性色视频| 久久成人精品视频| 久久九九免费| 老色鬼精品视频在线观看播放| 久久久xxx| 免费精品99久久国产综合精品| 你懂的国产精品永久在线| 欧美国产一区二区三区激情无套| 亚洲第一精品夜夜躁人人爽| 亚洲第一精品久久忘忧草社区| 亚洲欧洲在线播放| 一区二区免费在线视频| 午夜国产一区| 久久综合狠狠| 欧美日韩一区二区三区| 国产精品美女|