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

poj 1101

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

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

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

77 ,因為w,h最大值是75加上兩行外圍空地,最大開到77就可以了啊

但是結(jié)果卻是一直WA,困擾我很長時間,后來改到數(shù)組開到了100

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

供路過的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

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

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

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


只有注冊用戶登錄后才能發(fā)表評論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


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

導(dǎo)航

統(tǒng)計

公告

關(guān)于更多關(guān)于成大才子,請訪問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| 欧美大片国产精品| 亚洲欧洲在线看| 一本色道久久综合亚洲精品小说 | 亚洲日本成人网| 亚洲电影在线观看| 亚洲三级色网| 亚洲综合第一页| 久久成人羞羞网站| 你懂的成人av| 欧美日韩一区二区三区四区五区 | 亚洲国产欧美另类丝袜| av成人免费观看| 欧美呦呦网站| 欧美高清自拍一区| 国产精品亚发布| 亚洲第一福利视频| 亚洲婷婷综合久久一本伊一区| 西西裸体人体做爰大胆久久久| 久久av在线看| 亚洲国内在线| 欧美一区二区视频97| 亚洲性感激情| 亚洲欧美成人一区二区三区| 久久精品国产2020观看福利| 欧美 日韩 国产一区二区在线视频| 欧美久色视频| 韩国av一区二区三区在线观看| 亚洲人永久免费| 欧美一区日本一区韩国一区| 美日韩精品免费观看视频| 一区二区三区波多野结衣在线观看| 久久gogo国模啪啪人体图| 欧美婷婷在线| 亚洲欧洲日产国产综合网| 欧美在线观看日本一区| 亚洲欧洲日产国产网站| 久久久噜噜噜久噜久久| 国产精品一卡| 一区二区三区av| 欧美高清视频在线播放| 欧美中文字幕久久| 国产噜噜噜噜噜久久久久久久久 | 蜜桃伊人久久| 国产午夜精品全部视频在线播放| 99国内精品久久| 亚洲高清在线精品| 一区二区三区色| 欧美成人综合| 欧美性做爰毛片| 最近中文字幕mv在线一区二区三区四区| 亚洲男人影院| 亚洲人成啪啪网站| 久热这里只精品99re8久| 国产精品久久77777| 一区二区在线视频播放| 久久精品在线视频| 亚洲成在线观看| 国产亚洲精品美女| 欧美一区日本一区韩国一区| 99v久久综合狠狠综合久久| 美女脱光内衣内裤视频久久影院| 国产午夜亚洲精品羞羞网站 | 亚洲国产精品悠悠久久琪琪| 久久久久网址| 韩国欧美一区| 欧美xx69| 欧美精品一区二区三区蜜桃 | 亚洲区一区二区三区| 久久亚洲二区| 亚洲国产精品久久久久秋霞不卡| 久久久久久一区二区| 久久精品亚洲精品| 永久域名在线精品| 欧美国产91| 欧美三级在线视频| 久久国产免费| 久久亚洲高清| 一区二区av在线| 亚洲欧美美女| 亚洲欧洲一区| 一区二区高清视频在线观看| 欧美午夜视频网站| 亚洲国产成人91精品| 最近中文字幕mv在线一区二区三区四区| 欧美成人一区二免费视频软件| 亚洲日本成人| 亚洲视频精品| 好看的日韩视频| 亚洲黄色一区二区三区| 国产老肥熟一区二区三区| 欧美激情精品久久久久久免费印度 | 久久精品导航| 日韩视频在线一区| 亚洲欧美日韩国产另类专区| 尤妮丝一区二区裸体视频| 亚洲精品在线视频观看| 国产午夜一区二区三区| 亚洲国产日韩在线| 国产精品一区免费观看| 欧美激情精品久久久久久蜜臀| 国产精品成人v| 裸体素人女欧美日韩| 欧美日韩国产综合新一区| 另类天堂av| 国产乱肥老妇国产一区二| 亚洲精品美女在线| 1024国产精品| 亚洲欧美国产日韩中文字幕| 国内精品国产成人| 亚洲精品永久免费| 在线观看欧美精品| 亚洲午夜精品国产| 亚洲区第一页| 欧美亚洲在线观看| 亚洲一区二区在线观看视频| 欧美成人性生活| 欧美激情一区二区| 欧美大片91| 久久免费偷拍视频| 国产精品久久久久久一区二区三区 | 国产亚洲精品aa午夜观看| 亚洲另类自拍| 亚洲国产精品一区二区三区| 欧美一区二区三区视频免费播放 | 亚洲精品乱码久久久久久| 国产一区二区三区在线免费观看 | 亚洲一区二区三区在线看| 亚洲日本精品国产第一区| 欧美在现视频| 午夜精品视频一区| 国产精品久久一区二区三区| 一道本一区二区| 一本久久精品一区二区| 欧美国产免费| 亚洲精品国产系列| aa国产精品| 欧美视频三区在线播放| 一区二区高清在线| 欧美有码视频| 国产模特精品视频久久久久| 亚洲一区日本| 亚洲制服丝袜在线| 国产精品国产三级国产aⅴ无密码| 亚洲精品久久久久中文字幕欢迎你| 亚洲片在线观看| 亚洲欧美日韩另类| 午夜精品久久99蜜桃的功能介绍| 欧美日韩一区不卡| 亚洲网站在线观看| 亚洲欧美文学| 国产亚洲一区在线| 久久人人爽国产| 欧美夫妇交换俱乐部在线观看| 亚洲国产一区二区视频| 免费不卡中文字幕视频| 91久久久久久久久久久久久| 亚洲麻豆av| 国产精品ⅴa在线观看h| 亚洲在线视频| 久久先锋资源| 亚洲国产精品高清久久久| 欧美日韩国产a| 亚洲欧美日韩一区二区在线 | 欧美aⅴ一区二区三区视频| 欧美成人69av| 亚洲视频在线看| 激情综合在线| 欧美日韩国产片| 欧美一区二区三区在线观看视频 | 亚洲精品在线一区二区| 亚洲欧美在线视频观看| 韩国av一区二区三区在线观看| 欧美成人a∨高清免费观看| 一区二区日韩| 免费成人在线视频网站| 一本一道久久综合狠狠老精东影业| 国产伦精品一区二区三| 欧美高清在线精品一区| 香蕉久久一区二区不卡无毒影院| 欧美一区二区| 亚洲国产日韩欧美一区二区三区| 欧美性猛交99久久久久99按摩| 欧美在线精品一区| 99成人在线| 欧美成人精品一区二区三区| 国产亚洲欧美日韩精品| 欧美精品三级| 久久精品导航| 中日韩高清电影网| 最新成人在线| 欧美成人a视频| 六十路精品视频| 国产精品99久久久久久有的能看| 国产精品一区2区|