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

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>
            欧美成人一区二区| 亚洲一区免费视频| 欧美午夜免费影院| 最新日韩欧美| 亚洲精品乱码久久久久| 欧美高清在线观看| 亚洲免费电影在线观看| 亚洲欧美日韩第一区| 国产精品尤物| 久久久亚洲精品一区二区三区| 麻豆成人91精品二区三区| 亚洲狠狠丁香婷婷综合久久久| 欧美久久久久免费| 亚洲制服av| 欧美成人高清| 亚洲香蕉网站| 精品动漫一区| 欧美日韩亚洲天堂| 欧美尤物一区| 日韩午夜av| 久久久久中文| 亚洲一区图片| 亚洲国内精品| 国产日韩欧美高清免费| 欧美电影免费观看| 午夜精品区一区二区三| 91久久视频| 久久国产直播| 一片黄亚洲嫩模| 又紧又大又爽精品一区二区| 欧美日韩在线一区二区| 两个人的视频www国产精品| 亚洲视频在线播放| 欧美成在线视频| 久久九九国产精品怡红院| 亚洲小说欧美另类婷婷| 亚洲人成啪啪网站| 今天的高清视频免费播放成人| 国产精品久久久久影院色老大| 欧美激情第4页| 久久免费国产| 久久精品72免费观看| 亚洲一区二区精品在线观看| 国产精品免费看| 亚洲性夜色噜噜噜7777| 亚洲电影免费在线| 久久久精品日韩欧美| 一区二区三区www| 亚洲欧洲精品一区二区三区波多野1战4 | 欧美一级视频| 亚洲视频免费看| 亚洲精品乱码久久久久久蜜桃91| 欧美第十八页| 卡一卡二国产精品| 久久综合影视| 欧美不卡视频一区| 久久久久国产精品一区三寸 | 毛片av中文字幕一区二区| 久久精品国产第一区二区三区| 亚洲欧美高清| 欧美一区二区三区在线看| 亚洲欧美日韩在线不卡| 亚洲欧美国产va在线影院| 在线亚洲电影| 午夜在线不卡| 久久久久在线观看| 欧美xxx成人| 91久久夜色精品国产网站| 亚洲精品国产系列| 一本色道久久综合亚洲精品不卡 | 一本色道久久综合一区| 亚洲视频成人| 久久激情综合| 欧美第一黄网免费网站| 欧美日韩午夜剧场| 国产精品一级在线| 狠狠综合久久av一区二区小说| 91久久精品国产91性色| 日韩一区二区精品视频| 亚洲欧美激情视频在线观看一区二区三区| 亚洲视频在线一区观看| 性感少妇一区| 美女成人午夜| 日韩视频在线观看一区二区| 亚洲一级片在线看| 久久精品久久综合| 欧美高清视频一区二区三区在线观看| 欧美高清在线| 国产有码一区二区| 一本久久a久久精品亚洲| 在线亚洲国产精品网站| 性久久久久久久久久久久| 久久蜜臀精品av| 欧美高清视频在线播放| 国产精品无码专区在线观看| 一区二区三区无毛| 一区二区三区国产盗摄| 久久精品72免费观看| 亚洲国产三级| 新狼窝色av性久久久久久| 美女尤物久久精品| 国产精品毛片a∨一区二区三区| 韩国av一区二区| 亚洲愉拍自拍另类高清精品| 麻豆精品在线播放| 午夜精品国产更新| 欧美日韩国产不卡在线看| 韩日在线一区| 亚洲欧美日韩中文视频| 欧美激情一区二区三区在线| 欧美一区亚洲| 国产精品久久久久久久9999| 亚洲黄一区二区| 久久久久久久激情视频| 亚洲精品乱码久久久久| 久久久精彩视频| 国产精品天美传媒入口| 一区二区三区四区国产精品| 欧美91视频| 久久久97精品| 在线不卡视频| 久久综合精品国产一区二区三区| 亚洲视频观看| 欧美午夜精品理论片a级大开眼界| 亚洲精品日韩在线观看| 玖玖精品视频| 久久香蕉国产线看观看网| 国产亚洲精品一区二区| 久久精品国产99国产精品澳门| 午夜在线成人av| 国产亚洲一区二区三区| 久久久久久夜| 午夜精品久久久久久久白皮肤| 欧美三级视频| 午夜精品福利一区二区蜜股av| 亚洲天堂视频在线观看| 国产精品成人aaaaa网站| 日韩系列在线| 一区二区三区国产精品| 欧美日韩国产成人精品| 亚洲在线免费观看| 亚洲一级一区| 一区二区三区在线观看欧美| 久久亚洲综合网| 久久久免费精品视频| 国内外成人免费视频| 欧美mv日韩mv国产网站| 欧美国产乱视频| 亚洲一区精彩视频| 国产亚洲精品资源在线26u| 亚洲国产精品视频| 亚洲黄色有码视频| 欧美国产成人在线| 一本色道久久综合亚洲91| 一区二区黄色| 国产一区二区精品丝袜| 亚洲大胆av| 国产精品高清一区二区三区| 午夜综合激情| 暖暖成人免费视频| 亚洲无线观看| 欧美与黑人午夜性猛交久久久| 亚洲国产三级| 亚洲欧美999| 亚洲黄色毛片| 午夜精品久久久99热福利| 91久久在线播放| 亚洲午夜精品网| 亚洲黄页一区| 午夜亚洲精品| 中文日韩欧美| 久久婷婷成人综合色| 亚洲午夜成aⅴ人片| 久久精品人人做人人爽电影蜜月| 日韩视频二区| 久久精品99国产精品| 一区二区三区你懂的| 欧美一区二粉嫩精品国产一线天| 亚洲日韩中文字幕在线播放| 午夜精品999| 亚洲欧美日本精品| 欧美成人官网二区| 久久综合色天天久久综合图片| 欧美日韩在线三区| 欧美成人有码| 黄色免费成人| 篠田优中文在线播放第一区| 亚洲午夜未删减在线观看| 久久一区二区三区av| 久久成人精品视频| 国产精品第2页| 亚洲经典自拍| 91久久久久久久久久久久久| 久久久亚洲高清| 老司机久久99久久精品播放免费 | 欧美一区二区啪啪| 欧美在线影院| 国产精品网站在线| 亚洲午夜激情免费视频| 亚洲在线一区二区三区|