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

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)求各點(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á),說明存在墻將該點(diǎn)封閉起來,可以證明墻至少有一塊多余
 
*/
#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ù)  更多評論   

2010-01-15 22:08 by joy
灰常感謝LZ,看了你的第5條那個,讓debug了3個小時的我一下就過了;
因?yàn)槲业某跏蓟瓉硎?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在线| 久久影院午夜论| 欧美精品www在线观看| 欧美精品在线一区| 国产精品爽黄69| 国内精品久久久久影院薰衣草| 韩国av一区二区| 一片黄亚洲嫩模| 久久久久久综合| 一本色道综合亚洲| 久久精品国产99国产精品澳门| 久久久另类综合| 国产啪精品视频| 99国产精品久久久久久久久久 | 亚洲人久久久| 欧美一区亚洲| 欧美午夜激情在线| 亚洲精品中文字幕有码专区| 欧美伊人久久久久久久久影院 | 在线视频你懂得一区二区三区| 欧美电影在线| 免费成人性网站| 久久精品国语| 艳妇臀荡乳欲伦亚洲一区| 亚洲国产精品欧美一二99| 校园春色国产精品| 欧美一级理论片| 亚洲国产经典视频| 欧美欧美全黄| 亚洲欧美国产三级| av成人天堂| 国产精品扒开腿爽爽爽视频| 国产精品国内视频| 一区二区三区国产精华| 久久久久久有精品国产| 欧美一区二区| 在线免费观看欧美| 欧美激情国产日韩精品一区18| 欧美高清在线视频观看不卡| 久久精品亚洲热| 欧美在线播放一区二区| 激情综合色综合久久综合| 久久精品国产久精国产一老狼 | 国产麻豆91精品| 久久天堂国产精品| 久久久久久久久岛国免费| 亚洲欧洲综合另类| 亚洲小视频在线| 亚洲日韩视频| 久久av一区| 亚洲图片欧洲图片日韩av| 亚洲人成在线影院| 亚洲一区二区三区精品在线观看 | 国产欧美日韩91| 欧美国产视频日韩| 国产精品剧情在线亚洲| 亚洲福利av| 亚洲高清二区| 午夜精品久久久久99热蜜桃导演| 亚洲欧洲三级| 另类亚洲自拍| 免费成人毛片| 在线观看国产日韩| 羞羞漫画18久久大片| 欧美一区二区三区精品| 国产精品久久久久国产a级| 91久久综合亚洲鲁鲁五月天| 亚洲国产欧美一区| 欧美精品一区二区高清在线观看| 免费永久网站黄欧美| 樱花yy私人影院亚洲| 久久久777| 最新精品在线| 欧美一区二区三区视频免费播放| 欧美三级第一页| 午夜精品免费视频| 久久综合伊人| 亚洲一区视频在线| 国内精品模特av私拍在线观看| 久久精品99国产精品酒店日本| 久久蜜桃资源一区二区老牛| 亚洲丁香婷深爱综合| 欧美视频在线观看免费网址| 亚洲自拍啪啪| 亚洲电影观看| 久久精品日韩| 亚洲无线视频| 欧美一区二区三区在线视频 | 国产热re99久久6国产精品| 欧美资源在线观看| 亚洲另类春色国产| 久久久久九九九| 一区二区三区产品免费精品久久75 | 久久久亚洲综合| 这里只有精品视频在线| 国产欧美一区二区精品仙草咪 | 欧美激情中文字幕一区二区| 亚洲欧美国产日韩天堂区| 亚洲国产毛片完整版| 韩国av一区二区| 国产一区二区三区视频在线观看| 欧美理论在线播放| 欧美—级a级欧美特级ar全黄| 久久精品视频播放| 久热精品视频在线免费观看| 国产原创一区二区| 国产精品一区二区在线观看不卡| 欧美精品黄色| 欧美色中文字幕| 欧美日韩另类一区| 欧美精品一区二区在线播放| 欧美理论电影网| 欧美性色视频在线| 国产日韩精品一区二区三区| 国产精品嫩草99a| 国产一级揄自揄精品视频| 国产亚洲福利社区一区| 欧美一区=区| 久久久噜噜噜久久中文字幕色伊伊| 午夜精品婷婷| 麻豆国产精品va在线观看不卡| 欧美精品尤物在线| 国产精品剧情在线亚洲| 一区在线影院| 亚洲综合电影一区二区三区| 久久福利一区| 亚洲最新色图| 老司机免费视频一区二区| 欧美精品在线观看91| 国产手机视频一区二区| 日韩视频不卡中文| 巨胸喷奶水www久久久免费动漫| 亚洲精品视频一区| 久久免费视频观看| 国产欧美日韩综合一区在线观看| 亚洲三级视频在线观看| 久久国产精品99国产| 一本色道久久综合亚洲精品不 | 久久九九99| 9久草视频在线视频精品| 免费看的黄色欧美网站| 国产一区二区三区高清| 先锋影音久久| 欧美一区二区三区免费视频| 国产精品日韩在线一区| 亚洲欧美激情精品一区二区| 亚洲精品极品| 欧美日韩在线影院| 亚洲一区二区在线观看视频| 日韩小视频在线观看| 欧美三级不卡| 久久婷婷蜜乳一本欲蜜臀| 亚洲欧美成人精品| 国产精品伊人日日| 蘑菇福利视频一区播放| 欧美国产日韩xxxxx| 亚洲一区二区三区色| 欧美一区二区三区另类| 亚洲国产美女精品久久久久∴| 国产精品网红福利| 久久综合狠狠综合久久综青草| 久久国产精品久久国产精品| 亚洲精品乱码久久久久久按摩观 | 久久丁香综合五月国产三级网站| 欧美一区二区视频网站| 最新日韩欧美| 久久国产精品免费一区| 亚洲综合色丁香婷婷六月图片| 久久国产手机看片| 亚洲一级二级在线| 欧美精品二区| 欧美大片在线看免费观看| 国产精品精品视频| 亚洲欧洲精品天堂一级| 国内伊人久久久久久网站视频| 99国产一区| 在线一区二区三区做爰视频网站 | 亚洲欧美综合网| 亚洲欧洲日韩综合二区| 欧美一区2区三区4区公司二百 | 欧美在线免费视屏| 欧美xart系列在线观看| 国产视频一区欧美| 欧美一区二区三区电影在线观看| 一本大道久久a久久精二百| 久久嫩草精品久久久久| 亚洲黄色大片| 欧美国产亚洲视频|