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

            oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            Finding Nemo

            Posted on 2007-01-14 01:58 oyjpart 閱讀(1345) 評論(2)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

            Finding Nemo
            Time Limit:2000MS? Memory Limit:30000K
            Total Submit:1965 Accepted:370

            Description
            Nemo is a naughty boy. One day he went into the deep sea all by himself. Unfortunately, he became lost and couldn't find his way home. Therefore, he sent a signal to his father, Marlin, to ask for help.
            After checking the map, Marlin found that the sea is like a labyrinth with walls and doors. All the walls are parallel to the X-axis or to the Y-axis. The thickness of the walls are assumed to be zero.
            All the doors are opened on the walls and have a length of 1. Marlin cannot go through a wall unless there is a door on the wall. Because going through a door is dangerous (there may be some virulent medusas near the doors), Marlin wants to go through as few doors as he could to find Nemo.
            Figure-1 shows an example of the labyrinth and the path Marlin went through to find Nemo.


            We assume Marlin's initial position is at (0, 0). Given the position of Nemo and the configuration of walls and doors, please write a program to calculate the minimum number of doors Marlin has to go through in order to reach Nemo.

            Input
            The input consists of several test cases. Each test case is started by two non-negative integers M and N. M represents the number of walls in the labyrinth and N represents the number of doors.
            Then follow M lines, each containing four integers that describe a wall in the following format:
            x y d t
            (x, y) indicates the lower-left point of the wall, d is the direction of the wall -- 0 means it's parallel to the X-axis and 1 means that it's parallel to the Y-axis, and t gives the length of the wall.
            The coordinates of two ends of any wall will be in the range of [1,199].
            Then there are N lines that give the description of the doors:
            x y d
            x, y, d have the same meaning as the walls. As the doors have fixed length of 1, t is omitted.
            The last line of each case contains two positive float numbers:
            f1 f2
            (f1, f2) gives the position of Nemo. And it will not lie within any wall or door.
            A test case of M = -1 and N = -1 indicates the end of input, and should not be processed.

            Output
            For each test case, in a separate line, please output the minimum number of doors Marlin has to go through in order to rescue his son. If he can't reach Nemo, output -1.

            Sample Input

            8 9
            1 1 1 3
            2 1 1 3
            3 1 1 3
            4 1 1 3
            1 1 0 3
            1 2 0 3
            1 3 0 3
            1 4 0 3
            2 1 1
            2 2 1
            2 3 1
            3 1 1
            3 2 1
            3 3 1
            1 2 0
            3 3 0
            4 3 1
            1.5 1.5
            4 0
            1 1 0 1
            1 1 1 1
            2 1 1 1
            1 2 0 1
            1.5 1.7
            -1 -1

            Sample Output

            5
            -1

            第一次用priority_queue 發(fā)現(xiàn)效率還不錯(cuò)~
            居然1y了 很是驚訝的說 rp突然好起來了?
            我是從Nemo向Marlin搜索的 采用優(yōu)先隊(duì)列的方式就能找到最少的過門方式
            細(xì)節(jié)部分還是要注意~~
            Solution:
            //by Optimistic
            #include <stdio.h>
            #include <string.h>
            #include <queue>
            using namespace std;
            const int MAXINT = 2000000000;
            const int N = 210;
            struct Point{int x, y, p;}; //坐標(biāo),權(quán)值(經(jīng)過門的個(gè)數(shù))
            bool wall[N][N][2], door[N][N][2], end[N][N], seted[N][N]; //墻壁,門,可直達(dá)點(diǎn),標(biāo)記
            Point start;????????????????? //起點(diǎn)(Nemo)
            int nw, nd, xh, yh;?????????? //墻的個(gè)數(shù),門的個(gè)數(shù),x的最高值,y的最高值(限定搜索范圍)
            struct cmp
            {
            public: inline bool operator()(const Point& a, const Point& b) ?{return a.p > b.p;}
            };
            priority_queue <Point, vector<Point>, cmp> pq; //優(yōu)先隊(duì)列
            void set_end(int x, int y) //設(shè)置可直達(dá)點(diǎn)(不通過任何門)
            {
            ?end[x][y] = 1;
            ?if(x-1 <= xh && x-1 >= 0 && y <= yh && y >= 0 && wall[x][y][1] == 0?
            ??&& door[x][y][1] == 0 && !end[x-1][y])???set_end(x-1, y);
            ?if(x <= xh && x >= 0 && y-1 <= yh && y-1 >= 0 && wall[x][y][0] == 0
            ??&& door[x][y][0] == 0 && !end[x][y-1])???set_end(x, y-1);
            ?if(x+1 <= xh && x+1 >= 0 && y <= yh && y >= 0 && wall[x+1][y][1] == 0
            ??&& door[x+1][y][1] == 0 && !end[x+1][y])??set_end(x+1, y);
            ?if(x <= xh && x >= 0 && y+1 <= yh && y+1 >= 0 && wall[x][y+1][0] == 0
            ??&& door[x][y+1][0] == 0 && !end[x][y+1])??set_end(x, y+1);
            }?
            void init()
            {
            ?int i, x, y, d, t, j;
            ?double dx, dy;
            ?memset(wall, 0, sizeof(wall));
            ?memset(door, 0, sizeof(door));
            ?memset(end, 0, sizeof(end));
            ?yh = -MAXINT; xh = -MAXINT;
            ?for(i = 0; i<nw; i++) {
            ??scanf("%d%d%d%d", &x, &y, &d, &t);
            ??if(x > xh) xh = x;
            ??if(y > yh) yh = y;
            ??if(d == 0) {
            ???for(j = 0; j<t; j++) {
            ????wall[x+j][y][0] = 1;
            ???}
            ??}
            ??else {
            ???for(j = 0; j<t; j++) {
            ????wall[x][y+j][1] = 1;
            ???}
            ??}
            ?}
            ?for(i = 0; i<nd; i++) {
            ??scanf("%d%d%d", &x, &y, &d);
            ??if(x > xh) xh = x;
            ??if(y > yh) yh = y;
            ??door[x][y][d] = 1;
            ??wall[x][y][d] = 0;??? //門要把墻覆蓋 sample中可以看出來
            ?}
            ?cin >> dx >> dy;
            ?start.x = (int)dx, start.y = (int)dy, start.p = 0; //設(shè)置起點(diǎn) 初始化權(quán)值為0
            ?memset(seted, 0, sizeof(seted));
            ?set_end(0, 0); //設(shè)置可直達(dá)點(diǎn)(不通過任何門)
            ?yh++; xh++;
            }
            void work()
            {
            ?if(start.x < 0 || start.x >= 200 || start.y < 0 || start.y >= 200 || xh <0 || yh <0)? //特殊情況
            ?{?printf("0\n");??return ;?}
            ?memset(seted, 0, sizeof(seted));
            ?while(!pq.empty()) pq.pop();
            ?pq.push(start);??????????????????????? //起點(diǎn)入列
            ?seted[start.x][start.y] = 1;
            ?while(!pq.empty()) {
            ??Point cur = pq.top();????????????? //取權(quán)值最大的點(diǎn)
            ??pq.pop();
            ??if(end[cur.x][cur.y] == 1) { printf("%d\n", cur.p); return;} //找到解
            ??int x= cur.x, y = cur.y;
            ??Point now;
            ??if(x-1 <= xh && x-1 >= 0 && y <= yh && y >= 0 && wall[x][y][1] == 0 && !seted[x-1][y]) { //左搜索
            ???if(door[x][y][1] == 1) now.p = cur.p + 1;
            ???else now.p = cur.p;
            ???now.x = x -1;???now.y = y;
            ???pq.push(now);
            ??}
            ??if(x <= xh && x >= 0 && y - 1 <= yh && y-1 >= 0 && wall[x][y][0] == 0 && !seted[x][y-1]) { //下搜索
            ???if(door[x][y][0] == 1) now.p = cur.p + 1;
            ???else now.p = cur.p;
            ???now.x = x;???now.y = y-1;
            ???pq.push(now);
            ???seted[now.x][now.y] = 1;
            ??}
            ??if(x+1 <= xh && x+1 >= 0 && y <= yh && y >= 0 && wall[x+1][y][1] == 0 && !seted[x+1][y]) { //右搜索
            ???if(door[x+1][y][1] == 1) now.p = cur.p + 1;
            ???else now.p = cur.p;
            ???now.x = x + 1;???now.y = y;
            ???pq.push(now);
            ???seted[now.x][now.y] = 1;
            ??}
            ??if(x <= xh && x >= 0 && y+1 <= yh && y+1 >= 0 && wall[x][y+1][0] == 0 && !seted[x][y+1]) { //上搜索
            ???if(door[x][y+1][0] == 1) now.p = cur.p + 1;
            ???else now.p = cur.p;
            ???now.x = x;???now.y = y+1;
            ???pq.push(now);
            ???seted[now.x][now.y] = 1;
            ??}
            ?}
            ?printf("-1\n"); //無解
            }
            int main()
            {
            ?while(scanf("%d %d", &nw, &nd), !(nw == -1 && nd == -1)) {
            ??init();
            ??work();
            ?}
            ?return 0;
            }

            Feedback

            # re: Finding Nemo  回復(fù)  更多評論   

            2008-12-08 17:42 by lala
            拉拉,你左搜索忘標(biāo)記啦

            # re: Finding Nemo  回復(fù)  更多評論   

            2008-12-09 12:50 by alpc12
            好像是啊。。。汗。。
            久久亚洲高清综合| 色欲综合久久躁天天躁蜜桃| 久久国产精品偷99| 亚洲欧洲久久av| 精品久久久久久综合日本| 久久无码人妻精品一区二区三区 | 97久久久精品综合88久久| 中文精品久久久久国产网址| 亚洲国产成人精品女人久久久| 人妻无码αv中文字幕久久| 久久精品女人天堂AV麻| 中文字幕乱码人妻无码久久| 日韩亚洲欧美久久久www综合网 | 久久精品中文无码资源站| 青青青青久久精品国产h| 亚洲精品无码专区久久久| 青青青青久久精品国产h久久精品五福影院1421 | 91精品国产91热久久久久福利 | 久久久久人妻一区精品果冻| 欧美一区二区三区久久综| 91久久国产视频| 精品久久久久久成人AV| 久久天天躁狠狠躁夜夜不卡| 人妻无码久久精品| 国内精品久久久久久中文字幕| 国产亚洲欧美精品久久久| 99久久精品国产一区二区 | AV无码久久久久不卡网站下载| 女人高潮久久久叫人喷水| 久久精品无码专区免费| 精品久久人人爽天天玩人人妻| 99精品久久精品一区二区| 色婷婷综合久久久久中文| 久久精品无码午夜福利理论片| 久久亚洲AV成人无码| 久久这里有精品| 波多野结衣久久一区二区| 久久久久波多野结衣高潮| 亚洲日本va中文字幕久久| 香蕉久久av一区二区三区| 久久午夜伦鲁片免费无码|