没有合适的资源?快使用搜索试试~ 我知道了~
图算法例题1
需积分: 0 0 下载量 49 浏览量
2022-08-08
20:34:50
上传
评论
收藏 76KB DOCX 举报
温馨提示
试读
38页
图算法例题1
资源推荐
资源详情
资源评论
图算法例题
1000. sicily 1155. Can I Post the lette .......................................................................................2
1001. 无路可逃? ...................................................................................................................4
1002. connect components in undirected graph......................................................................6
1003. bicoloring ........................................................................................................................8
1004. Knight Moves ..................................................................................................................9
1005. 有向图边的分类 .........................................................................................................12
1006. DAG? .............................................................................................................................15
1007. sicily . Magic Island .......................................................................................................17
1008. Forest ............................................................................................................................19
1009. sicily 1424. 奖金...........................................................................................................22
1011. sicily 1090. Highways ....................................................................................................26
1012. Robot ............................................................................................................................31
1013. sicily 1031. Campus.......................................................................................................34
图算法例题
1000. sicily 1155. Can I Post the lette
Time Limit: 1sec Memory Limit:32MB
Description
I am a traveler. I want to post a letter to Merlin. But because there are so many roads I can walk
through, and maybe I can’t go to Merlin’s house following these roads, I must judge whether I
can post the letter to Merlin before starting my travel.
Suppose the cities are numbered from 0 to N-1, I am at city 0, and Merlin is at city N-1. And there
are M roads I can walk through, each of which connects two cities. Please note that each road is
direct, i.e. a road from A to B does not indicate a road from B to A.
Please help me to find out whether I could go to Merlin’s house or not.
Input
There are multiple input cases. For one case, first are two lines of two integers N and M, (N<=200,
M<=N*N/2), that means the number of citys and the number of roads. And Merlin stands at city
N-1. After that, there are M lines. Each line contains two integers i and j, what means that there
is a road from city i to city j.
The input is terminated by N=0.
Output
For each test case, if I can post the letter print “I can post the letter” in one line, otherwise print
“I can't post the letter”.
Sample Input
3
2
0 1
1 2
3
1
0 1
0
Sample Output
I can post the letter
I can't post the letter
Source Code
#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<int> vout[200];
bool visited[200];
bool flood(int u)
{
visited[u]=1;
if (u==n-1) return 1;
for (int x=0; x<vout[u].size(); x++)
{
int &v=vout[u][x];
if (!visited[v] && flood(v)) return 1;
}
return 0;
}
int main()
{
while (cin>>n, n)
{
fill(vout,vout+n,vector<int>());
fill(visited,visited+n,0);
cin>>m;
while (m--)
{
int u,v;
cin>>u>>v;
vout[u].push_back(v);
}
cout<<(flood(0)?"I can post the letter\n":"I can't post the
letter\n");
}
return 0;
}
1001. 无路可逃?
Time Limit: 1sec Memory Limit:256MB
Description
唐僧被妖怪关在迷宫中。孙悟空好不容易找到一张迷宫地图,并通过一个魔法门来到来到迷
宫某个位置。假设迷宫是一个 n*m 的矩阵,它有两种地形,1 表示平地,0 表示沼泽,孙悟
空只能停留在平地上。孙悟空目前的位置在坐标(sx,sy)处,他可以向上下左右四个方向移动。
请你帮助孙悟空计算一下,迷宫中是否存在一条路从他所在位置(sx,sy)到达唐僧所在位置
(tx,ty)?
Input
输入第一行为一个整数 t(0<t<=10),表示测试用例个数。
每个测试样例的第 1 行是 2 个正整数 n (1≤n≤100),m (1≤n≤100),表示迷宫是 n*m 的矩
阵。接下来的 n 行输入迷宫,每行有 m 个数字(0 或者 1),数字之间用一个空格间隔。
接下来的 1 行是 4 个整数 sx,sy,tx,ty,1≤sx,tx≤n,1≤sy,ty≤m,表示孙悟空所在位置为第 sx
行第 sy 列,唐僧所在位置为第 tx 行第 tx 列。迷宫左上角编号是(1,1),右下角编号是(n, m)。
数据保证(sx,sy)格和(tx,ty)必定为平地。
Output
每个样例单独输出一行:1 表示路径存在,0 表示路径不存在。
Sample Input
2
2 2
1 0
0 1
1 1 2 2
4 4
1 1 1 0
1 0 1 1
1 0 1 1
1 1 1 0
1 1 3 4
Sample Output
0
1
Source Code
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 110;
int maze[MAXN][MAXN];
struct point {
int x, y;
point(int a=0, int b=0) : x(a), y(b) {}
};
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main()
{
int i, j, t, sx, sy, tx, ty, head, tail, n, m;
scanf("%d", &t);
while (t--)
{
queue<point> cq;
scanf("%d%d", &n, &m);
for (i=0;i<n;++i) {
for (j=0;j<m;++j) scanf("%d", &maze[i][j]);
}
scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
--sx; --sy; --tx; --ty;
maze[sx][sy] = -1;
cq.push(point(sx,sy));
while (!cq.empty())
{
point cur = cq.front();
cq.pop();
for (i=0;i<4;++i) {
point tar = cur;
tar.x += dx[i];
tar.y += dy[i];
if (tar.x < 0 || tar.x >= n || tar.y < 0 || tar.y >= m)
continue;
if (maze[tar.x][tar.y] <= 0) continue;
maze[tar.x][tar.y] = -1;
cq.push(tar);
}
}
if (maze[tx][ty] >= 0) puts("0"); else puts("1");
}
return 0;
}
剩余37页未读,继续阅读
资源评论
鸣泣的海猫
- 粉丝: 22
- 资源: 293
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- python开心麻花影视作品分析程序+源码.zip
- pythonExcel数据分析师程序+源码.zip
- PlatformUI.jar 支持RCP控件环境插件
- VB+ACCESS大型机房学生上机管理系统(源代码+系统).zip
- 基于BP神经网络的回归分析,基于优化动量因子的BP神经网络,基于优化学习率的BP神经网络,基于优化隐藏层神经元的bp神经网络
- python读取excel数据Python-file-reading-master.zip
- STC15单片机串口2使用程序例子
- 读取日志的excel生成周报 用python3开发weekplan-master.zip
- python 读取excel数据导入dbimport-data-master.zip
- K折交叉验证BP神经网络,多输入多输出BP神经网络(代码完整,数据齐全)
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功