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

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) 評論(1)  編輯 收藏 引用 所屬分類: OJ
/**
 * (1)求各點到源點的最小步數(BFS)
 * (2)求各點到終點的最小步數(BFS)
 * (3)如果點不是給定路徑上的點,那么:該點到源點的最小步數+該點到終點的最小步數<給定路徑的步數,否則給定路徑不是唯一最短的
 * (4)如果兩相鄰點a、b之間存在墻,那么:a到源點的最小步數+1+b到終點的最小步數<=給定路徑的步數
 *                              或者 a到終點的最小步數+1+b到源點的最小步數<=給定路徑的步數,否則墻多余
 * (5)如果存在點不可達,說明存在墻將該點封閉起來,可以證明墻至少有一塊多余
 
*/
#include 
<iostream>
#include 
<string>
#include 
<queue>
using namespace std;

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

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)
    {
        
// 初始化數據
        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;
        }

        
// 求各點到源點的最小步數(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();
        }

        
// 求各點到終點的最小步數(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;     // 是否有封閉區域
                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[未登錄]  回復  更多評論   

2010-01-15 22:08 by joy
灰常感謝LZ,看了你的第5條那個,讓debug了3個小時的我一下就過了;
因為我的初始化原來是-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>
            亚洲欧美在线一区| 蜜臀av一级做a爰片久久| 久久久久网站| 久久精品99国产精品| 久久国产综合精品| 噜噜噜躁狠狠躁狠狠精品视频 | 国产精品免费一区二区三区在线观看| 欧美日韩精品国产| 国产精品视频免费观看www| 国产香蕉97碰碰久久人人| 一区视频在线| 国产精品99久久久久久久久久久久 | 亚洲毛片av在线| 亚洲午夜视频| 麻豆精品精华液| 国产精品久久福利| 亚洲国产精品一区二区久| 在线一区二区三区四区五区| 久久精品一区| 亚洲精品小视频| 午夜精品一区二区三区电影天堂 | 久久精品亚洲一区二区三区浴池| 欧美不卡激情三级在线观看| 99亚洲视频| 久久资源在线| 国产日韩欧美精品| 一区二区三区色| 欧美大色视频| 久久久人成影片一区二区三区| 欧美一级片久久久久久久| 欧美成人免费全部| 国产一区美女| 午夜精品一区二区三区电影天堂 | 在线欧美三区| 欧美亚洲综合在线| 亚洲精品精选| 久久午夜精品一区二区| 国产精品美腿一区在线看| 99热这里只有成人精品国产| 久久青青草综合| 亚洲摸下面视频| 欧美性一区二区| 一本色道久久综合狠狠躁篇的优点 | 久久精品女人天堂| 亚洲影院一区| 欧美视频中文一区二区三区在线观看| 亚洲高清免费在线| 美女久久一区| 久久久国产精品一区二区三区| 国产精品卡一卡二| 亚洲一区二区三区中文字幕| 亚洲精品日韩激情在线电影| 欧美激情亚洲| 一区二区三区高清在线| 亚洲韩日在线| 欧美绝品在线观看成人午夜影视| 亚洲第一网站免费视频| 美女任你摸久久| 免费短视频成人日韩| 亚洲大胆人体在线| 亚洲电影专区| 欧美日韩另类在线| 亚洲无毛电影| 亚洲一区二区三区精品在线观看| 国产精品久久久久7777婷婷| 亚洲永久免费观看| 亚洲一区二区三区免费在线观看 | 国产亚洲午夜高清国产拍精品| 午夜精品理论片| 欧美一级电影久久| 亚洲第一黄色| 亚洲人成人77777线观看| 欧美日韩国产免费观看| 亚洲午夜小视频| 午夜亚洲性色视频| 在线精品视频一区二区三四| 欧美69视频| 欧美日韩另类在线| 欧美日韩在线三级| 在线不卡亚洲| 亚洲激情国产精品| 欧美日韩在线播放| 性伦欧美刺激片在线观看| 久久不见久久见免费视频1| 伊人夜夜躁av伊人久久| 亚洲精品少妇网址| 韩曰欧美视频免费观看| 亚洲国产一二三| 国产三区精品| 亚洲精美视频| 国产综合久久久久久| 亚洲人成小说网站色在线 | 亚洲国产成人在线播放| 亚洲国产黄色| 国产伦精品一区二区三| 欧美激情欧美狂野欧美精品| 欧美午夜宅男影院在线观看| 久久久综合视频| 欧美日韩和欧美的一区二区| 久久精品视频免费观看| 欧美日韩成人在线视频| 久久影院亚洲| 国产精品你懂的| 欧美高清不卡| 国产三级精品三级| 亚洲精品一区二区三区av| 国产亚洲精品aa| 99re66热这里只有精品3直播| 国语自产在线不卡| 亚洲天堂网站在线观看视频| 亚洲人成毛片在线播放| 欧美影片第一页| 欧美一区二区久久久| 欧美人与性禽动交情品| 欧美大片一区二区三区| 国产欧美日韩一级| 亚洲一区二区在线| 亚洲视频在线观看视频| 欧美成人高清视频| 噜噜爱69成人精品| 黄色成人av网| 久久精品国产精品亚洲精品| 午夜伦理片一区| 国产精品v欧美精品∨日韩| 亚洲欧洲三级| 亚洲精品影院| 欧美韩日一区| 亚洲国产导航| 亚洲精品久久久一区二区三区| 久久国产精品一区二区三区四区| 欧美一区二区三区在线观看视频| 国产精品美女久久久久久免费 | 亚洲主播在线观看| 国产精品啊啊啊| 亚洲一区二区高清视频| 欧美一级电影久久| 国产网站欧美日韩免费精品在线观看 | 欧美a级片网| 有坂深雪在线一区| 久久久久久久999精品视频| 久久久久国产精品一区| 国产一区二区三区四区| 欧美在线高清视频| 欧美国产先锋| 99热免费精品| 欧美三级视频| 午夜国产精品影院在线观看| 久久精品国产亚洲5555| 韩日成人在线| 欧美精品日韩精品| 亚洲一二三四区| 久久天天躁夜夜躁狠狠躁2022| 国内精品视频一区| 欧美大胆人体视频| 中文久久精品| 开元免费观看欧美电视剧网站| 精品999在线观看| 欧美精品v日韩精品v韩国精品v | 亚洲自拍电影| 国产一区二区成人| 欧美成人一区在线| 亚洲一区欧美| 欧美国产日韩一区二区三区| 99一区二区| 国产午夜一区二区三区| 欧美a级一区| 亚洲欧美中文另类| 欧美激情亚洲另类| 西西人体一区二区| 亚洲美女免费精品视频在线观看| 国产精品久久久久久五月尺| 久久久之久亚州精品露出| 日韩亚洲不卡在线| 欧美1区视频| 久久精品国产久精国产一老狼| 亚洲美女毛片| 在线观看视频一区二区| 国产精品黄页免费高清在线观看| 久久久久久久久伊人| 一区二区三区鲁丝不卡| 欧美大片在线观看一区| 久久精品国产久精国产爱| 国产精品99久久久久久有的能看 | 日韩视频―中文字幕| 久久国产精品亚洲77777| 99国内精品久久久久久久软件| 国产精品一区二区三区免费观看| 麻豆91精品| 欧美亚洲视频一区二区| 亚洲国产视频一区| 欧美成人69av| 久久精品国产2020观看福利| 亚洲色无码播放| 亚洲精品日韩精品| 欲色影视综合吧| 国产一区二区三区日韩欧美| 国产精品美女久久久久久2018| 欧美韩日一区二区| 老司机亚洲精品| 久久久久久久久久久一区|