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

單鏈DNA

換了個地址:http://www.cnblogs.com/vizhen/

 

HDOJ 1010 Tempter of the Bone--DFS+奇偶剪枝

      題目原文:http://acm.hdu.edu.cn/showproblem.php?pid=1010

      題目大意:給出起始位置和終點位置,要求在指定的時間剛好到達終點時間,每移動一步一秒,并且不能返回。   

      題目分析:

                  1。起初以為能用BFS做,后來發現,必須在指定的時間內抵達終點才行,BFS無法達到要求。

                  2。要求在指定時間內到達,唯一想法就是能不能枚舉出所有抵達方案,再在通過檢查時間時間是否吻合,得到結果,這就自然想到了用DFS進行搜索。

                  3。DFS搜索完成后,提交發現超時,看樣子還得剪枝才行,無奈啊,百度一下。

                  4。剪枝方法:奇偶剪枝

                             把map看作

                             0 1 0 1 0 1
                             1 0 1 0 1 0
                             0 1 0 1 0 1
                             1 0 1 0 1 0
                             0 1 0 1 0 1

                       從 0->1 需要奇數步

                       從 0->0 需要偶數步
                       那么設所在位置 (x,y) 與 目標位置 (dx,dy)

                       如果abs(x-y)+abs(dx-dy)為偶數,則說明 abs(x-y) 和 abs(dx-dy)的奇偶性相同,需要走偶數步

                       如果abs(x-y)+abs(dx-dy)為奇數,那么說明 abs(x-y) 和 abs(dx-dy)的奇偶性不同,需要走奇數步

                       理解為 abs(si-sj)+abs(di-dj) 的奇偶性就確定了所需要的步數的奇偶性!!

                       而 (ti-setp)表示剩下還需要走的步數,由于題目要求要在 ti時 恰好到達,那么  (ti-step) 與 abs(x-y)+abs(dx-dy) 的奇偶性必須相同

                       因此 temp=ti-step-abs(dx-x)-abs(dy-y) 必然為偶數!

                5。最后一點:整個圖的可以移動步數應該大于指定的時間

#include "iostream"
#include <math.h>
using namespace std;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int n,m;
char a[7][7];
int sx,sy,dx,dy;
int ti,flag;
void DfsSerch(int x,int y,int step)
{
/////////////////////////////////////
int temp;
temp=ti-step-abs(dx-x)-abs(dy-y);
if (temp<0||temp%2==1) return;
////////////////////////////////////
int tx,ty;
for(int i=0;i<4;i++)  //方向探索
{
tx=x+dir[i][0];
ty=y+dir[i][1];
if (a[tx][ty]=='D'&&step==ti-1)
{
flag=1;
return ;
}
if(a[tx][ty]=='.'&&(tx>=0&&tx<n)
&&(ty>=0&&ty<m))
{
a[tx][ty]='X';  //標記訪問 
DfsSerch(tx,ty,step+1);
a[tx][ty]='.';  //回溯取消標記
if(flag==1) return;//找到直接返回
}
}
}
int main()
{
while (cin>>n>>m>>ti&&n!=0||m!=0||ti!=0)
{
///////////////////////////////////////
//輸入數據
int wall=0;
for (int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>a[i][j];
if(a[i][j]=='S')
{
sx=i;
sy=j;
}
if (a[i][j]=='D')
{
dx=i;
dy=j;
}
if (a[i][j]=='X')
{
wall++;
}
}//for-for
/////////////////////////////////////
flag=0;
if (n*m-wall<=ti)
{
cout<<"NO"<<endl;
continue;
}
DfsSerch(sx,sy,0);
if(flag==1)
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}

posted on 2010-04-26 17:20 Geek.tan 閱讀(1971) 評論(0)  編輯 收藏 引用 所屬分類: ACM解題報告

導航

統計

公告

coding是我的寂寞,我是誰的寂寞

隨筆分類(40)

隨筆檔案(48)

搜索

積分與排名

最新評論

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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| 亚洲精品影院在线观看| 老司机一区二区三区| 91久久一区二区| 最新日韩精品| 国产精品入口福利| 久久婷婷成人综合色| 久久午夜激情| 一区二区欧美日韩视频| 亚洲主播在线播放| 在线观看日韩欧美| 亚洲韩国青草视频| 国产精品高潮呻吟久久av无限 | 亚洲精品国精品久久99热一| 亚洲精品视频二区| 国产热re99久久6国产精品| 久久综合狠狠| 欧美精品麻豆| 久久精品99久久香蕉国产色戒| 麻豆成人综合网| 亚洲一区网站| 另类av一区二区| 欧美一区不卡| 欧美精品在欧美一区二区少妇| 欧美怡红院视频| 欧美成年人视频网站| 香蕉av777xxx色综合一区| 久久综合久久88| 欧美亚洲免费电影| 欧美大片国产精品| 久久久久久999| 国产精品a久久久久| 麻豆国产va免费精品高清在线| 欧美性猛交99久久久久99按摩| 狂野欧美一区| 国产欧美日韩一区二区三区| 亚洲精品一二三| 亚洲高清视频的网址| 亚洲欧美日韩在线高清直播| 一区二区三区产品免费精品久久75| 久久精品国产免费| 午夜精品久久久久久久久| 欧美成人综合网站| 免费在线播放第一区高清av| 国产日韩欧美夫妻视频在线观看| 亚洲高清视频的网址| 韩国一区电影| 欧美一区二区三区精品| 亚洲午夜久久久久久久久电影院 | 欧美中文在线观看| 午夜精品国产更新| 欧美三级视频| 亚洲最新视频在线| 亚洲小说欧美另类社区| 欧美大片网址| 欧美国内亚洲| 亚洲欧洲久久| 欧美激情亚洲自拍| 亚洲精品久久久久久久久久久久| 亚洲精品美女91| 欧美成人性生活| 亚洲激情专区| 日韩视频免费观看高清在线视频 | 国产真实精品久久二三区| 亚洲欧美精品在线| 欧美一区二区三区四区在线观看地址 | 亚洲欧洲精品一区二区三区波多野1战4 | 最新国产の精品合集bt伙计| 美日韩精品视频| 欧美激情在线有限公司| 亚洲精品一二区| 欧美日韩美女一区二区| 在线视频日本亚洲性| 午夜精品久久久久久久久久久久| 国产欧美二区| 久久精品日产第一区二区| 欧美成人午夜激情在线| 亚洲人午夜精品免费| 欧美日韩国语| 午夜精品视频在线观看一区二区| 久久久久久穴| 亚洲精品国久久99热| 欧美三区在线| 欧美在线网址| 亚洲高清一二三区| 亚洲欧美精品在线观看| 国内精品亚洲| 欧美激情aⅴ一区二区三区| 日韩一区二区高清| 久久嫩草精品久久久精品一| 亚洲国产欧美日韩精品| 欧美日韩aaaaa| 香蕉av777xxx色综合一区| 蜜臀av一级做a爰片久久| 99精品久久久| 国产一区二区三区日韩| 欧美国产日韩二区| 亚洲免费一级电影| 亚洲大片免费看| 性做久久久久久久免费看| 亚洲国产精品一区二区www| 国产精品久久国产精品99gif | 欧美视频一区| 看欧美日韩国产| 亚洲一区二区三区影院| 欧美激情第二页| 欧美一区二区黄| 亚洲最新视频在线| 一区二区在线视频播放| 国产精品电影观看| 免费成人av资源网| 羞羞视频在线观看欧美| 亚洲欧洲精品一区二区三区| 久久人91精品久久久久久不卡| 亚洲天堂免费在线观看视频| 在线视频成人| 国产在线精品一区二区中文| 欧美日韩综合| 欧美成人一区二区在线| 久久久人成影片一区二区三区| 亚洲视频一区二区在线观看| 亚洲国产日韩欧美| 美女主播精品视频一二三四| 久久国产精品电影| 亚洲综合成人在线| 宅男噜噜噜66一区二区| 亚洲精品一区二区三区四区高清| 激情六月婷婷综合| 国产视频一区在线观看| 国产精品一区二区久久久 | 久久精品毛片| 午夜宅男久久久| 亚洲一区二区视频| 一区二区免费在线播放| 亚洲精品中文字幕在线| 亚洲三级免费| 日韩午夜视频在线观看| 亚洲精品视频在线看| 亚洲人成77777在线观看网| 亚洲成色777777女色窝| 欧美电影免费网站| 亚洲成人在线视频播放| 狂野欧美性猛交xxxx巴西| 久久裸体艺术| 欧美成人精品激情在线观看| 噜噜爱69成人精品| 欧美成人免费小视频| 亚洲国产成人久久综合一区| 亚洲欧洲一区二区天堂久久| 亚洲精选一区| 亚洲一区二区日本| 欧美一区二区三区日韩| 欧美在线你懂的| 久久伊人免费视频| 欧美黄色免费网站| 欧美午夜宅男影院| 国产日韩一区二区三区| 在线精品福利| 夜夜嗨av一区二区三区中文字幕| 中国日韩欧美久久久久久久久| 亚洲欧美日韩成人| 久久久伊人欧美| 亚洲国产合集| 亚洲一区二区免费| 久久久精品国产免大香伊| 欧美电影免费网站| 国产精品每日更新| 樱桃国产成人精品视频| 日韩视频在线观看免费| 欧美一区永久视频免费观看| 麻豆成人综合网| 99这里只有精品| 欧美在线一级va免费观看| 欧美激情一区二区三区蜜桃视频| 国产精品国产一区二区| 伊人蜜桃色噜噜激情综合| aa级大片欧美| 久久久久久久尹人综合网亚洲| 亚洲激情不卡| 欧美在线视频导航| 欧美日韩视频免费播放| 黑丝一区二区三区| 亚洲综合第一| 亚洲国产视频一区二区| 欧美一区国产在线| 欧美特黄一级| 亚洲黄色一区| 久久久久天天天天| 夜夜嗨av一区二区三区免费区| 久久一区二区精品| 国产欧美一区二区三区国产幕精品| 最新国产成人av网站网址麻豆| 欧美影片第一页| 一本大道久久a久久精二百| 麻豆精品一区二区av白丝在线| 国产乱理伦片在线观看夜一区| 日韩视频永久免费| 欧美大尺度在线| 久久精品盗摄|