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

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>
            久久夜色精品国产欧美乱极品 | 欧美激情a∨在线视频播放| 国产精品成人av性教育| 亚洲第一中文字幕| 亚洲视频免费看| 国产午夜久久| 欧美精品免费观看二区| 欧美在线观看视频在线| 亚洲欧洲一区二区三区在线观看| 午夜日本精品| 亚洲激情视频网站| 欧美四级电影网站| 欧美一级欧美一级在线播放| 久久亚洲影院| 久久久久国产一区二区三区四区| 最新日韩中文字幕| 亚洲国产成人久久综合| 狠狠色综合日日| 欧美va天堂| 暖暖成人免费视频| 欧美99久久| 亚洲国产日韩在线一区模特| 欧美成黄导航| 欧美高潮视频| 91久久极品少妇xxxxⅹ软件| 欧美成人影音| 亚洲精品乱码久久久久久蜜桃麻豆 | 欧美不卡视频| 久久精品国产69国产精品亚洲| 亚洲欧美日韩一区| 欧美在线视频导航| 亚洲韩国青草视频| 亚洲三级免费观看| 亚洲一区二区三区四区五区午夜| 亚洲最黄网站| 久久精品亚洲国产奇米99| 麻豆精品一区二区综合av| 欧美激情网友自拍| 伊人狠狠色丁香综合尤物| 亚洲激精日韩激精欧美精品| 亚洲一区中文字幕在线观看| 老鸭窝91久久精品色噜噜导演| 亚洲国产天堂久久综合| 亚洲在线观看视频| 免费一级欧美片在线播放| 日韩视频免费在线| 久久婷婷一区| 午夜在线精品偷拍| 久久久久久午夜| 国产精品色婷婷久久58| 亚洲免费观看高清在线观看 | 午夜精品久久久久久久99热浪潮 | 免费观看成人鲁鲁鲁鲁鲁视频| 午夜在线成人av| 亚洲国产精品高清久久久| 亚洲风情在线资源站| 欧美私人网站| 男女精品视频| 国产精品久久久久久久9999| 久久久一区二区三区| 欧美三级日本三级少妇99| 欧美一区三区三区高中清蜜桃| 久久男人资源视频| 欧美一级电影久久| 欧美精品一区二区在线观看| 久久成人在线| 国产精品日韩久久久久| 亚洲黄色在线看| 在线观看一区| 久久久久久久久久久久久女国产乱| 亚洲最新中文字幕| 欧美aaa级| 久久综合综合久久综合| 国产精品亚洲精品| 亚洲图片在线| 欧美在线一区二区三区| 国产精品理论片在线观看| 黄色成人av网| 麻豆精品传媒视频| 欧美国产日韩视频| 亚洲精品日韩在线| 欧美日本免费一区二区三区| 亚洲三级影片| 亚洲欧美国产日韩中文字幕| 欧美日韩综合在线| 99re6这里只有精品| 亚洲永久视频| 狠狠色综合网| 欧美乱大交xxxxx| 亚洲一级黄色| 免费成人你懂的| 一区二区三区国产| 国产一区二区在线免费观看| 久久视频在线视频| 亚洲精品一区二区三区婷婷月| 亚洲制服av| 亚洲国产高潮在线观看| 欧美日韩无遮挡| 久久久7777| 日韩小视频在线观看| 久久久亚洲欧洲日产国码αv | 中日韩美女免费视频网站在线观看| 亚洲一区二区三区精品视频 | 浪潮色综合久久天堂| 一本一本久久| 欧美激情一区二区三区全黄| 午夜精品一区二区三区电影天堂 | 欧美日韩一区二区国产| 久久精品视频在线播放| 日韩亚洲欧美成人| 欧美jizzhd精品欧美巨大免费| 欧美剧在线观看| 欧美一区国产二区| 99在线观看免费视频精品观看| 欧美国产免费| 欧美激情小视频| 亚洲国产一区二区三区在线播| 久久aⅴ国产欧美74aaa| 欧美一区激情| 久久久女女女女999久久| 久久精品一区二区三区不卡牛牛| 午夜电影亚洲| 久久亚洲精品一区二区| 免费久久99精品国产自在现线| 久久精品国产一区二区电影| 久久久国产一区二区三区| 久久乐国产精品| 欧美~级网站不卡| 亚洲国产精品女人久久久| 亚洲人成欧美中文字幕| 99精品福利视频| 亚洲欧美一区二区原创| 久久九九精品99国产精品| 免费亚洲电影| 国产日韩欧美一区二区三区在线观看 | 国产偷国产偷亚洲高清97cao| 国产精品一区二区a| 黄色成人在线免费| 一本大道久久精品懂色aⅴ| 欧美在线精品一区| 亚洲精品乱码久久久久久蜜桃麻豆 | 亚洲一区在线看| 浪潮色综合久久天堂| 一本色道久久精品| 久久免费的精品国产v∧| 欧美日韩免费观看一区=区三区| 国产情侣一区| 午夜视频一区二区| 亚洲免费av观看| 欧美高清一区二区| 黄色一区二区三区| 久久久九九九九| 欧美一级理论性理论a| 国产精品欧美精品| 亚洲一区二区三区四区五区午夜 | 久久精品国产久精国产爱| 亚洲国产一区在线观看| 久久综合久久久久88| 一区久久精品| 亚洲成人资源网| 美日韩免费视频| 91久久精品网| 亚洲美女视频在线观看| 欧美精品午夜| 亚洲免费在线| 久久不射2019中文字幕| 国产视频在线一区二区| 久久青草久久| 欧美精品一区二区三区四区| 亚洲一区二区四区| 性做久久久久久免费观看欧美| 国产欧美日韩一区二区三区在线| 先锋影音网一区二区| 久久久久国产精品人| 亚洲久色影视| 久久aⅴ国产紧身牛仔裤| 最新中文字幕亚洲| 亚洲综合色噜噜狠狠| 1024成人| 香蕉免费一区二区三区在线观看| 亚洲高清毛片| 午夜视黄欧洲亚洲| 在线亚洲自拍| 欧美国产日韩a欧美在线观看| 欧美视频在线观看免费网址| 久久国产精品一区二区| 欧美高清视频在线播放| 久久久久国产一区二区三区| 欧美视频在线播放| 亚洲精品乱码| 日韩天堂av| 欧美aⅴ99久久黑人专区| 欧美福利一区| 亚洲区在线播放| 欧美激情一区二区三区在线| 欧美aa在线视频| 亚洲精品乱码久久久久久蜜桃91| 久久精品系列| 欧美xx69| 亚洲天堂男人|