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

lzm

who dare win.
posts - 14, comments - 29, trackbacks - 0, articles - 0

poj 1024 Tester Program

Posted on 2009-03-19 08:59 lzmagic 閱讀(952) 評(píng)論(1)  編輯 收藏 引用 所屬分類: OJ
/**
 * (1)求各點(diǎn)到源點(diǎn)的最小步數(shù)(BFS)
 * (2)求各點(diǎn)到終點(diǎn)的最小步數(shù)(BFS)
 * (3)如果點(diǎn)不是給定路徑上的點(diǎn),那么:該點(diǎn)到源點(diǎn)的最小步數(shù)+該點(diǎn)到終點(diǎn)的最小步數(shù)<給定路徑的步數(shù),否則給定路徑不是唯一最短的
 * (4)如果兩相鄰點(diǎn)a、b之間存在墻,那么:a到源點(diǎn)的最小步數(shù)+1+b到終點(diǎn)的最小步數(shù)<=給定路徑的步數(shù)
 *                              或者 a到終點(diǎn)的最小步數(shù)+1+b到源點(diǎn)的最小步數(shù)<=給定路徑的步數(shù),否則墻多余
 * (5)如果存在點(diǎn)不可達(dá),說(shuō)明存在墻將該點(diǎn)封閉起來(lái),可以證明墻至少有一塊多余
 
*/
#include 
<iostream>
#include 
<string>
#include 
<queue>
using namespace std;

struct Grid
{
    
bool inpath;    // 是否是路徑方格
    bool uwal;      // 是否有上墻
    bool rwal;      // 是否有右墻
    int scnt;       // 到源點(diǎn)步數(shù)
    int dcnt;       // 到終點(diǎn)步數(shù)
};

int main(int argc, char** argv)
{
    
bool ok;
    
int w, h, cnt, steps;   // 1 <= w, h <= 100
    string path;
    Grid grid[
100][100];
    queue
<pair<intint> > q;

    
int t, x, y, desx, desy, x2, y2, i;
    
for (cin >> t; t > 0--t)
    {
        
// 初始化數(shù)據(jù)
        cin >> w >> h;
        
for (y = 0; y < h; ++y)
            
for (x = 0; x < w; ++x)
            {
                grid[y][x].inpath 
= false;
                grid[y][x].uwal 
= false;
                grid[y][x].rwal 
= false;
                grid[y][x].scnt 
= -1;
                grid[y][x].dcnt 
= -1;
            }
        cin 
>> path;
        x 
= 0, y = 0;
        grid[
0][0].inpath = true;
        steps 
= path.size();
        
for (i = 0; i < steps; ++i)
        {
            
switch(path[i])
            {
                
case 'U'++y; break;
                
case 'D'--y; break;
                
case 'L'--x; break;
                
case 'R'++x; break;
            }
            grid[y][x].inpath 
= true;
        }
        desx 
= x, desy = y;
        cin 
>> cnt;
        
for (i = 0; i < cnt; ++i)
        {
            cin 
>> x >> y >> x2 >> y2;
            
if (x == x2)
                
if (y + 1 == y2) grid[y][x].uwal = true;
                
else grid[y2][x].uwal = true;
            
else
                
if (x + 1 == x2) grid[y][x].rwal = true;
                
else grid[y][x2].rwal = true;
        }

        
// 求各點(diǎn)到源點(diǎn)的最小步數(shù)(BFS)
        q.push(make_pair(00));
        grid[
0][0].scnt = 0;
        
while (!q.empty())
        {
            y 
= q.front().first, x = q.front().second;
            
if (y < h - 1 && grid[y][x].uwal == false && grid[y + 1][x].scnt == -1)
            {
                grid[y 
+ 1][x].scnt = grid[y][x].scnt + 1;
                q.push(make_pair(y 
+ 1, x));
            }
            
if (0 < y && grid[y - 1][x].uwal == false && grid[y - 1][x].scnt == -1)
            {
                grid[y 
- 1][x].scnt = grid[y][x].scnt + 1;
                q.push(make_pair(y 
- 1, x));
            }
            
if (0 < x && grid[y][x - 1].rwal == false && grid[y][x - 1].scnt == -1)
            {
                grid[y][x 
- 1].scnt = grid[y][x].scnt + 1;
                q.push(make_pair(y, x 
- 1));
            }
            
if (x < w - 1 && grid[y][x].rwal == false && grid[y][x + 1].scnt == -1)
            {
                grid[y][x 
+ 1].scnt = grid[y][x].scnt + 1;
                q.push(make_pair(y, x 
+ 1));
            }
            q.pop();
        }

        
// 求各點(diǎn)到終點(diǎn)的最小步數(shù)(BFS)
        q.push(make_pair(desy, desx));
        grid[desy][desx].dcnt 
= 0;
        
while (!q.empty())
        {
            y 
= q.front().first, x = q.front().second;
            
if (y < h - 1 && grid[y][x].uwal == false && grid[y + 1][x].dcnt == -1)
            {
                grid[y 
+ 1][x].dcnt = grid[y][x].dcnt + 1;
                q.push(make_pair(y 
+ 1, x));
            }
            
if (0 < y && grid[y - 1][x].uwal == false && grid[y - 1][x].dcnt == -1)
            {
                grid[y 
- 1][x].dcnt = grid[y][x].dcnt + 1;
                q.push(make_pair(y 
- 1, x));
            }
            
if (0 < x && grid[y][x - 1].rwal == false && grid[y][x - 1].dcnt == -1)
            {
                grid[y][x 
- 1].dcnt = grid[y][x].dcnt + 1;
                q.push(make_pair(y, x 
- 1));
            }
            
if (x < w - 1 && grid[y][x].rwal == false && grid[y][x + 1].dcnt == -1)
            {
                grid[y][x 
+ 1].dcnt = grid[y][x].dcnt + 1;
                q.push(make_pair(y, x 
+ 1));
            }
            q.pop();
        }

        
// 判斷路徑是否唯一最短,以及墻是否多余
        ok = true;
        
for (y = 0; y < h && ok; ++y)
            
for (x = 0; x < w && ok; ++x)
            {
                
if (grid[y][x].scnt == -1 || grid[y][x].dcnt == -1)
                    ok 
= false;     // 是否有封閉區(qū)域
                if (y < h - 1 && grid[y][x].uwal
                        
&& grid[y][x].scnt + grid[y + 1][x].dcnt + 1 > steps
                        
&& grid[y][x].dcnt + grid[y + 1][x].scnt + 1 > steps)
                    ok 
= false;     // 是否上墻多余
                if (x < w - 1 && grid[y][x].rwal
                        
&& grid[y][x].scnt + grid[y][x + 1].dcnt + 1 > steps
                        
&& grid[y][x].dcnt + grid[y][x + 1].scnt + 1 > steps)
                    ok 
= false;     // 是否右墻多余
                if (!grid[y][x].inpath && grid[y][x].scnt + grid[y][x].dcnt <= steps)
                    ok 
= false;     // 是否存在更短路徑或另一最短路徑
            }
        
if(ok) cout << "CORRECT" << endl;
        
else cout << "INCORRECT" << endl;
    }

    
return 0;
}



Feedback

# re: poj 1024 Tester Program[未登錄]  回復(fù)  更多評(píng)論   

2010-01-15 22:08 by joy
灰常感謝LZ,看了你的第5條那個(gè),讓debug了3個(gè)小時(shí)的我一下就過了;
因?yàn)槲业某跏蓟瓉?lái)是-1,所以釀成杯具啊。。
這bug。。汗。
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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精品免费视频| 久久美女性网| 亚洲日本aⅴ片在线观看香蕉| 国产精品chinese| 日韩亚洲欧美在线观看| 欧美一二三区精品| 亚洲欧美日韩精品一区二区| 欧美日韩福利视频| 亚洲欧美三级伦理| 欧美在线视频播放| 亚洲三级影片| 亚洲午夜一级| 国产在线一区二区三区四区 | 亚洲国产日韩在线一区模特| 蜜桃av综合| 一区二区高清在线| 午夜日韩激情| 亚洲乱码久久| 性做久久久久久免费观看欧美| 欧美日韩成人一区二区| 一区二区三区av| 亚洲一区精彩视频| 亚洲黄色三级| 亚洲香蕉视频| 亚洲精品国产精品久久清纯直播| 99视频一区二区| 在线观看视频亚洲| 一区二区国产精品| 亚洲二区在线| 亚洲一本视频| 亚洲理论在线观看| 欧美一区国产一区| 亚洲婷婷国产精品电影人久久 | 久久精品人人爽| 欧美成人午夜激情在线| 欧美日韩亚洲成人| 美女视频黄a大片欧美| 欧美国产综合| 久久精品91久久香蕉加勒比| 欧美成人精品在线观看| 久久狠狠久久综合桃花| 欧美日本久久| 欧美黑人在线观看| 国内揄拍国内精品久久| 一区二区高清视频在线观看| 91久久在线播放| 久久九九国产精品| 国产精品99久久久久久久久久久久| 午夜精品剧场| 亚洲欧美日本精品| 欧美日韩精品三区| 亚洲国产成人av在线| 国产原创一区二区| 亚洲欧美日本精品| 亚洲综合电影一区二区三区| 欧美国产精品v| 久久精品国产久精国产爱| 国产精品爱啪在线线免费观看| 亚洲国产精彩中文乱码av在线播放| 国产欧美一区二区三区国产幕精品 | 欧美成人一区二区三区| 亚洲一区二区三区在线播放| 老司机午夜精品视频| 国产欧美日韩专区发布| 久久久久久9| 久久久国产精品亚洲一区 | 在线视频精品一| 欧美特黄一级| 免费看成人av| 欧美国产丝袜视频| 欧美大片免费| 亚洲精品久久久久久久久| 亚洲国产毛片完整版| 亚洲国产毛片完整版 | 国产精品久久国产三级国电话系列| 久热精品在线| 亚洲第一在线综合网站| 欧美有码视频| 欧美日韩精品一区二区三区| 亚洲精品免费在线播放| 亚洲欧洲一区二区三区在线观看| 麻豆成人小视频| 亚洲国产精品专区久久| 洋洋av久久久久久久一区| 欧美涩涩视频| 亚洲免费小视频| 久久婷婷成人综合色| 亚洲第一中文字幕| 亚洲黄页一区| 亚洲视频香蕉人妖| 国产精品一区视频| 久久精品国产精品亚洲| 欧美国产综合一区二区| 一区二区三区蜜桃网| 国产精品视频一| 久热re这里精品视频在线6| 亚洲国产另类精品专区| 亚洲福利在线看| 亚洲欧美另类在线观看| 黄色精品网站| 欧美午夜精品久久久久免费视| 亚洲一区精彩视频| 欧美韩国日本一区| 亚洲免费在线播放| 亚洲国产aⅴ天堂久久| 欧美日韩免费看| 久久精品一区二区三区中文字幕| 亚洲激情第一区| 久久久亚洲一区| 亚洲午夜极品| 亚洲乱码国产乱码精品精| 欧美日韩一区在线观看视频| 欧美一区二区三区四区在线| 亚洲国产精品综合| 久久婷婷蜜乳一本欲蜜臀| 欧美大秀在线观看| 欧美与黑人午夜性猛交久久久| 亚洲国产成人精品久久久国产成人一区 | 欧美顶级艳妇交换群宴| 99在线精品免费视频九九视| 久久中文欧美| 羞羞答答国产精品www一本 | 欧美高清视频在线观看| 午夜精品亚洲| 一区二区三区成人精品| 欧美国产大片| 久久夜色精品国产亚洲aⅴ| 亚洲在线观看视频网站| 亚洲欧洲精品一区二区| 韩日精品视频一区| 国产婷婷97碰碰久久人人蜜臀| 欧美乱大交xxxxx| 免费在线国产精品| 久久精品亚洲一区二区| 香蕉久久国产| 亚洲欧美国产日韩天堂区| 日韩午夜电影在线观看| 91久久视频| 亚洲国产精品一区二区第四页av | 欧美中文在线观看国产| 亚洲一区在线观看免费观看电影高清| 亚洲精品日产精品乱码不卡| 在线观看一区视频| 永久域名在线精品| 精品51国产黑色丝袜高跟鞋| 亚洲综合第一页| 亚洲一级片在线看| 亚洲色无码播放| 中文一区二区在线观看| 一区二区三区视频在线| 中文一区二区| 亚洲第一中文字幕在线观看| 亚洲欧美日韩精品综合在线观看| 一区二区精品| 亚洲视频视频在线| 中国av一区| 午夜影院日韩| 久久视频在线视频| 欧美大片在线看免费观看| 欧美精品入口| 国产精品你懂的| 韩国欧美国产1区| 最新日韩中文字幕| 亚洲五月婷婷| 久久久久久久一区| 欧美福利视频在线观看| 亚洲精品少妇| 亚洲视频一区| 欧美在线看片a免费观看| 性欧美超级视频| 久久人人看视频| 欧美日韩一区二区视频在线观看 | 国产精品扒开腿爽爽爽视频| 国产色爱av资源综合区| 1024欧美极品| 亚洲在线一区| 美女任你摸久久| 夜夜嗨av色一区二区不卡| 欧美一区二区视频97| 欧美国产日韩一区二区在线观看| 欧美视频一区在线观看| 好吊色欧美一区二区三区四区| 亚洲另类视频| 久久久国产午夜精品| 亚洲精品之草原avav久久| 亚洲一区二区三区乱码aⅴ蜜桃女| 亚洲综合精品一区二区| 久久久精品2019中文字幕神马| 亚洲黄色在线视频| 欧美中文字幕视频| 欧美日韩网址| 亚洲电影免费观看高清| 亚洲欧美视频| 91久久线看在观草草青青| 久久精品国产久精国产爱| 中日韩视频在线观看| 在线观看亚洲视频啊啊啊啊| 中文精品在线| 亚洲国产精品小视频|