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

oyjpArt ACM/ICPC算法程序設計空間

// 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 閱讀(1354) 評論(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 發現效率還不錯~
居然1y了 很是驚訝的說 rp突然好起來了?
我是從Nemo向Marlin搜索的 采用優先隊列的方式就能找到最少的過門方式
細節部分還是要注意~~
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;}; //坐標,權值(經過門的個數)
bool wall[N][N][2], door[N][N][2], end[N][N], seted[N][N]; //墻壁,門,可直達點,標記
Point start;????????????????? //起點(Nemo)
int nw, nd, xh, yh;?????????? //墻的個數,門的個數,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; //優先隊列
void set_end(int x, int y) //設置可直達點(不通過任何門)
{
?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; //設置起點 初始化權值為0
?memset(seted, 0, sizeof(seted));
?set_end(0, 0); //設置可直達點(不通過任何門)
?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);??????????????????????? //起點入列
?seted[start.x][start.y] = 1;
?while(!pq.empty()) {
??Point cur = pq.top();????????????? //取權值最大的點
??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  回復  更多評論   

2008-12-08 17:42 by lala
拉拉,你左搜索忘標記啦

# re: Finding Nemo  回復  更多評論   

2008-12-09 12:50 by alpc12
好像是啊。。。汗。。
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲黄页视频免费观看| 欧美激情在线观看| 亚洲欧美在线观看| 国产精品区一区| 久久精品视频在线观看| 欧美综合国产| 亚洲精品欧洲| 亚洲一区一卡| 亚洲第一区中文99精品| 亚洲精品视频在线| 国产三区二区一区久久| 免费成人av在线看| 欧美日韩色婷婷| 久久久久九九视频| 欧美精品成人一区二区在线观看 | 亚洲国产精品久久久久秋霞不卡| 亚洲高清自拍| 国产精品一二三| 欧美成人在线免费视频| 国产精品porn| 欧美国产极速在线| 国产深夜精品福利| 亚洲清纯自拍| 一区二区在线观看视频在线观看 | 欧美一级黄色网| 男同欧美伦乱| 久久久久免费视频| 欧美视频在线观看 亚洲欧| 免费观看成人| 国产日韩欧美一区| 夜夜夜精品看看| 亚洲欧洲中文日韩久久av乱码| 亚洲午夜小视频| 亚洲精品国久久99热| 欧美在线观看一区二区| 亚洲天堂网在线观看| 欧美va日韩va| 麻豆精品精华液| 国产欧美日韩精品一区| 日韩一级裸体免费视频| 亚洲日本欧美在线| 久久永久免费| 久久亚洲精品伦理| 国产午夜精品一区二区三区视频 | 亚洲一区二区久久| 亚洲午夜91| 欧美激情黄色片| 亚洲国产第一页| 在线观看欧美亚洲| 久久国产一区二区| 久久久久一本一区二区青青蜜月| 欧美亚洲成人精品| 一本久道久久综合狠狠爱| 亚洲日本欧美天堂| 欧美成人在线免费观看| 欧美激情按摩| 亚洲精品小视频| 你懂的成人av| 最近中文字幕mv在线一区二区三区四区| 黄色成人在线网站| 久久精品卡一| 欧美a级一区二区| 亚洲丰满在线| 欧美高清在线精品一区| 欧美激情中文字幕在线| 亚洲精品久久久久久久久久久久 | 亚洲国产免费看| 欧美成人一区二区在线| 亚洲国产欧美国产综合一区| 亚洲激情av| 欧美日韩精品在线视频| 夜夜精品视频| 欧美亚洲一级片| 国内一区二区三区| 麻豆乱码国产一区二区三区| 亚洲欧洲另类国产综合| 亚洲图中文字幕| 国产日韩欧美在线一区| 猛男gaygay欧美视频| 亚洲精品麻豆| 久久成人精品一区二区三区| 激情视频亚洲| 欧美日韩成人一区二区三区| 亚洲深爱激情| 久久综合免费视频影院| 亚洲毛片在线免费观看| 国产精品乱人伦一区二区| 欧美一区二粉嫩精品国产一线天| 玖玖精品视频| 亚洲午夜精品一区二区三区他趣| 国产日韩欧美不卡| 欧美aaa级| 亚洲午夜性刺激影院| 蜜臀av性久久久久蜜臀aⅴ| 亚洲精品一区二区三区福利| 国产精品美女久久久久av超清 | 香蕉国产精品偷在线观看不卡| 麻豆精品国产91久久久久久| 在线视频你懂得一区 | 欧美gay视频| 亚洲综合首页| 亚洲国产婷婷| 久久九九久久九九| 亚洲午夜伦理| 亚洲国产精品t66y| 国产欧美一区二区精品秋霞影院| 久久免费黄色| 香蕉久久夜色精品| 亚洲老司机av| 欧美激情精品久久久久久蜜臀| 亚洲欧美999| 亚洲伦伦在线| 亚洲高清视频一区二区| 国产日韩欧美精品一区| 国产精品v欧美精品v日韩| 欧美成人久久| 久久国产夜色精品鲁鲁99| 亚洲一级免费视频| 日韩视频不卡| 亚洲经典一区| 欧美成人精品一区| 久久躁狠狠躁夜夜爽| 午夜欧美大尺度福利影院在线看| 日韩亚洲欧美综合| 在线观看日韩av| 精品9999| 黄色一区二区在线观看| 国产一区二区三区久久悠悠色av| 欧美亚州韩日在线看免费版国语版| 欧美韩日一区| 欧美国产日韩精品免费观看| 美日韩精品免费观看视频| 久久艳片www.17c.com| 久久久精品tv| 久久蜜桃资源一区二区老牛 | 亚洲美女91| 亚洲黄网站在线观看| 亚洲国内自拍| 亚洲日本成人在线观看| 亚洲美女免费视频| 99精品免费网| 亚洲一区二区三区免费观看| 亚洲香蕉在线观看| 亚洲欧美日韩精品久久久| 午夜精品成人在线视频| 欧美一区二区三区在线播放| 久久精品色图| 美女露胸一区二区三区| 欧美精品免费看| 国产精品狠色婷| 国产精品羞羞答答| 狠狠色2019综合网| 91久久精品国产| 亚洲一区二区视频在线| 亚洲欧美怡红院| 久久九九精品| 亚洲福利久久| 一区二区三区欧美在线| 亚洲在线一区二区| 久久久精品久久久久| 欧美极品在线观看| 国产精品久久久久久久久久ktv| 国产精品另类一区| 亚洲第一狼人社区| 亚洲淫性视频| 老司机精品久久| 亚洲麻豆av| 欧美一区二区三区在线观看| 麻豆国产va免费精品高清在线| 欧美日韩免费精品| 国外成人在线视频网站| 亚洲另类在线一区| 久久精品免费观看| 亚洲欧洲视频在线| 欧美一区激情| 欧美日韩不卡| 韩国成人理伦片免费播放| 日韩视频在线观看| 久久九九久久九九| 一级日韩一区在线观看| 久久精品天堂| 国产精品视频免费| 亚洲精品乱码久久久久| 久久精品成人| 99精品福利视频| 欧美不卡高清| 国产视频精品xxxx| 宅男精品视频| 亚洲高清三级视频| 欧美怡红院视频| 国产精品劲爆视频| 亚洲精品在线电影| 欧美jizzhd精品欧美巨大免费| 亚洲一级二级在线| 欧美日韩1区2区| 91久久午夜| 欧美成人午夜77777| 先锋影音久久| 国产美女一区二区| 午夜久久电影网|