• <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>

            misschuer

            常用鏈接

            統(tǒng)計(jì)

            積分與排名

            百事通

            最新評(píng)論

            hdu 1175 連連看

            #include <iostream>
            #define MAXN 1001
            #include 
            <queue>
            using namespace std;

            int mat[MAXN][MAXN];
            int mark[MAXN][MAXN];
            int n, m, sx, sy, ex, ey, q;
            //int mov[ 4 ][ 2 ] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
            //搜索的順序影響結(jié)果
            int mov[ 4 ][ 2 ] = {{01}, {10}, {0-1}, {-10}};

            struct Node {
                
                
            int x;
                
            int y;
                
            int turn;
                
            int dir;
            };

            void BFS() {
                 
                queue
            <Node> Q;
                Node p, q;
                p.x 
            = sx;   p.y = sy;
                mark[ sx ][ sy ] 
            = 0;
                p.dir 
            = -1; p.turn = 0;

                Q.push(p);
                
                
            while(!Q.empty()) {
                    
                    q 
            = Q.front();
                    Q.pop();

                    
            if(q.x == ex && q.y == ey) {
                        
                        puts(
            "YES");
                        
            return ;
                    }
                    
                    
            //0下, 1上, 2左, 3右
                    for(int i = 0; i < 4++ i) {
                    
                        p.x 
            = q.x + mov[ i ][ 0 ];
                        p.y 
            = q.y + mov[ i ][ 1 ];
                        p.turn 
            = q.turn;
                        p.dir 
            = q.dir;
                        
                        
            if(q.dir == -1) {
                           
                            p.dir 
            = i;
                            p.turn 
            = 0;
                        }
                        
            else if(q.dir != i) {
                            
                            p.turn 
            ++;
                            p.dir 
            = i;
                        }


                        
            if(p.x < 1 || p.x > n || p.y < 1 || p.y > m) continue;

                        
            if(mat[ p.x ][ p.y ] && !(p.x == ex && p.y == ey) || p.turn > 2continue;
                        


                        
            if(mark[ p.x ][ p.y ] > p.turn) {
                
                            mark[ p.x ][ p.y ] 
            = p.turn;
                            Q.push(p);
                        }
                    }
                }
                
                puts(
            "NO");
            }

            void res() {
                
                
                scanf(
            "%d"&q);
                
            while(q --) {
                    
                    scanf(
            "%d %d %d %d"&sx, &sy, &ex, &ey);
                    
            if(sx == ex && sy == ey) {
                    
                        puts(
            "NO");
                        
            continue;
                    }

                    
            if(mat[ sx ][ sy ] != mat[ ex ][ ey ] || mat[ sx ][ sy ] == 0 || mat[ ex ][ ey ] == 0) {
                    
                        puts(
            "NO");
                        
            continue;
                    }

                    
            for(int i = 1; i <= n; ++ i) {
                    
                        
            for(int j = 1; j <= m; ++ j) {
                        
                            mark[ i ][ j ] 
            = 10000000;
                        }
                    }

                    BFS();
                }
            }

            int main() {
                
                
                
            while(~scanf("%d %d"&n, &m)) {
                    
                    
            if(n == 0 && m == 0break;
                    
                    
            for(int i = 1; i <= n; ++ i) {
                        
                        
            for(int j = 1; j <= m; ++ j) {
                            
                            scanf(
            "%d"&mat[ i ][ j ]);
                        }
                    }
                    res();
                }
                
            return 0;
            }

            posted on 2011-03-17 12:16 此最相思 閱讀(804) 評(píng)論(4)  編輯 收藏 引用

            評(píng)論

            # re: hdu 1175 連連看[未登錄](méi) 2011-05-06 20:59 Xy

            你的代碼WA的
              回復(fù)  更多評(píng)論   

            # re: hdu 1175 連連看 2011-07-21 11:03 ahfywff

            你的代碼有一點(diǎn)小問(wèn)題,下面這組測(cè)試數(shù)據(jù)的結(jié)果應(yīng)該是“YES”

            3 4
            1 0 0 2
            0 0 0 0
            2 2 2 1
            1
            1 1 3 4

            代碼中的 if(mark[ p.x ][ p.y ] > p.turn) 應(yīng)該改為 if(mark[ p.x ][ p.y ] >= p.turn)  回復(fù)  更多評(píng)論   

            # re: hdu 1175 連連看 2011-08-13 14:50 misschuer

            @Xy
            我表示剛看到 然后測(cè)試了一下 可以過(guò)的吧
              回復(fù)  更多評(píng)論   

            # re: hdu 1175 連連看 2011-08-13 14:54 misschuer

            由于HDU的數(shù)據(jù)不強(qiáng)所以 代碼是有點(diǎn)錯(cuò)誤  回復(fù)  更多評(píng)論   


            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            精品视频久久久久| 乱亲女H秽乱长久久久| 伊人久久国产免费观看视频| 久久亚洲熟女cc98cm| 久久国产精品99国产精| 999久久久免费国产精品播放| 久久99国产精品一区二区| 久久无码精品一区二区三区| 亚洲中文字幕无码久久2017| 久久青草国产手机看片福利盒子| 三级片免费观看久久| 国产精品免费看久久久| 亚洲一级Av无码毛片久久精品| 欧美黑人激情性久久| 伊人热热久久原色播放www| 久久99精品国产麻豆宅宅| 久久久久久国产精品无码下载| 国产精品9999久久久久| 伊人精品久久久久7777| 91久久香蕉国产熟女线看| 久久夜色精品国产欧美乱| 亚洲AⅤ优女AV综合久久久| 日韩亚洲欧美久久久www综合网| 久久精品一本到99热免费| 久久99久久无码毛片一区二区| 99久久无色码中文字幕| 亚洲AV日韩精品久久久久久 | 久久久久青草线蕉综合超碰| 国产成人无码精品久久久免费| 99久久99久久精品免费看蜜桃| 久久天天躁狠狠躁夜夜2020一 | 97超级碰碰碰碰久久久久| 久久久精品国产sm调教网站 | 91精品日韩人妻无码久久不卡| 91精品国产综合久久久久久| 久久99精品国产自在现线小黄鸭| 亚洲精品乱码久久久久久中文字幕| 久久精品免费一区二区| 亚洲午夜久久久久久久久电影网| 久久久久久午夜精品| 久久免费看黄a级毛片|