POJ1573 ZOJ1708 UVA10116 UVALive5334 HDU1035 Robot Motion【模拟】

2024-04-08 19:58

本文主要是介绍POJ1573 ZOJ1708 UVA10116 UVALive5334 HDU1035 Robot Motion【模拟】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Robot Motion
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 16166 Accepted: 7643
Description
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0K1yHoGJ-1614299697840)(http://poj.org/images/1573_1.jpg)]

A robot has been programmed to follow the instructions in its path. Instructions for the next direction the robot is to move are laid down in a grid. The possible instructions are

N north (up the page)
S south (down the page)
E east (to the right on the page)
W west (to the left on the page)

For example, suppose the robot starts on the north (top) side of Grid 1 and starts south (down). The path the robot follows is shown. The robot goes through 10 instructions in the grid before leaving the grid.

Compare what happens in Grid 2: the robot goes through 3 instructions only once, and then starts a loop through 8 instructions, and never exits.

You are to write a program that determines how long it takes a robot to get out of the grid or how the robot loops around.

Input

There will be one or more grids for robots to navigate. The data for each is in the following form. On the first line are three integers separated by blanks: the number of rows in the grid, the number of columns in the grid, and the number of the column in which the robot enters from the north. The possible entry columns are numbered starting with one at the left. Then come the rows of the direction instructions. Each grid will have at least one and at most 10 rows and columns of instructions. The lines of instructions contain only the characters N, S, E, or W with no blanks. The end of input is indicated by a row containing 0 0 0.

Output

For each grid in the input there is one line of output. Either the robot follows a certain number of instructions and exits the grid on any one the four sides or else the robot follows the instructions on a certain number of locations once, and then the instructions on some number of locations repeatedly. The sample input below corresponds to the two grids above and illustrates the two forms of output. The word “step” is always immediately followed by “(s)” whether or not the number before it is 1.

Sample Input

3 6 5
NEESWE
WWWESS
SNWWWW
4 5 1
SESWE
EESNW
NWEEN
EWSEN
0 0 0

Sample Output

10 step(s) to exit
3 step(s) before a loop of 8 step(s)
Source

Mid-Central USA 1999

Regionals 1999 >> North America - Mid-Central USA

问题链接:POJ1573 ZOJ1708 UVA10116 UVALive5334 HDU1035 Robot Motion
问题简述:(略)
问题分析
    有r*c区域,机器人从第一行的某列进入,该区域全部由’N’ , ‘S’ , ‘W’ , ‘E’ ,走到某个区域的时候只能按照该区域指定的方向进行下一步,计算机器人能否走出该片区域,若不能则输出开始绕圈的步数和圈的大小。
    这个问题有2种解法,DFS和BFS都可以。用BFS来解时,需要用STL的队列来辅助。
之前的代码过于繁琐,另外写了一个解题程序。用模拟来实现,模拟走迷宫直到走出迷宫。用数组mcnt[][]记住走了几步就可以了。
程序说明:(略)
参考链接:(略)
题记:(略)

AC的C++语言程序如下:

/* POJ1573  ZOJ1708 UVA10116 UVALive5334 Robot Motion */#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;const int N = 10;
char maze[N][N + 1];
int mcnt[N][N];int main()
{int r, c, r2, c2;while(scanf("%d%d%d", &r, &c, &c2) && (r || c || c2)) {for(int i = 0; i < r; i++)scanf("%s", maze[i]);memset(mcnt, 0, sizeof(mcnt));int cnt = 1;r2 = 0, c2--;while(mcnt[r2][c2] == 0 && r2 >= 0 && r2 < r && c2 >= 0 && c2 < c) {mcnt[r2][c2] = cnt++;if(maze[r2][c2] == 'N') r2--;else if(maze[r2][c2] == 'S') r2++;else if(maze[r2][c2] == 'W') c2--;else if(maze[r2][c2] == 'E') c2++;}if(r2 >= 0 && r2 < r && c2 >= 0 && c2 < c)printf("%d step(s) before a loop of %d step(s)\n", mcnt[r2][c2] - 1, cnt - mcnt[r2][c2]);else printf("%d step(s) to exit\n", cnt - 1);}return 0;
}

AC的C语言程序(HDU以外,DFS)如下:

/* POJ1573  ZOJ1708 UVA10116 UVALive5334 Robot Motion */#include <stdio.h>
#include <string.h>#define N 10
char maze[N][N + 1];
int vis[N][N], step[N][N], r, c, cnt;void dfs(int row, int col)
{cnt++;if(row < 0 || row >= r || col < 0 || col >= c)printf("%d step(s) to exit\n", cnt);else if(vis[row][col])printf("%d step(s) before a loop of %d step(s)\n", step[row][col], cnt - step[row][col]);else {vis[row][col] = 1;step[row][col] = cnt;if(maze[row][col] == 'S') dfs(row + 1, col);if(maze[row][col] == 'N') dfs(row - 1, col);if(maze[row][col] == 'E') dfs(row, col + 1);if(maze[row][col] == 'W') dfs(row, col - 1);}
}int main(void)
{int enter, i;while(scanf("%d%d%d", &r, &c, &enter) && (r || c || enter)) {for(i = 0; i < r; i++)scanf("%s", maze[i]);memset(vis, 0, sizeof(vis));cnt = -1;dfs(0, enter - 1);}return 0;
}

AC的C语言程序(HDU,DFS)如下:

/* HDU1035 Robot Motion */#include <stdio.h>
#include <string.h>#define N 10
char maze[N][N + 1];
int vis[N][N], step[N][N], r, c, cnt;void dfs(int row, int col)
{cnt++;if(row < 0 || row >= r || col < 0 || col >= c)printf("%d step(s) to exit\n", cnt);else if(vis[row][col])printf("%d step(s) before a loop of %d step(s)\n", step[row][col], cnt - step[row][col]);else {vis[row][col] = 1;step[row][col] = cnt;if(maze[row][col] == 'S') dfs(row + 1, col);if(maze[row][col] == 'N') dfs(row - 1, col);if(maze[row][col] == 'E') dfs(row, col + 1);if(maze[row][col] == 'W') dfs(row, col - 1);}
}int main(void)
{int enter, i;while(scanf("%d%d", &r, &c) && (r || c)) {scanf("%d", &enter);for(i = 0; i < r; i++)scanf("%s", maze[i]);memset(vis, 0, sizeof(vis));cnt = -1;dfs(0, enter - 1);}return 0;
}

AC的C++语言程序(HDU以外,BFS)如下:

/* POJ1573  ZOJ1708 UVA10116 UVALive5334 Robot Motion */#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>using namespace std;const int N = 10;
char maze[N][N + 1];
bool vis[N][N];
int step[N][N], r, c, enter, cnt;struct Node {int row, col;Node(int r = 0, int c = 0) : row(r), col(c) {}
};void bfs()
{memset(vis, false, sizeof(vis));step[0][enter - 1] = 0;queue<Node> q;q.push(Node(0, enter - 1));int cnt = -1;while(!q.empty()) {Node t = q.front();q.pop();cnt++;if(t.row < 0 || t.row >= r || t.col < 0 || t.col >= c)printf("%d step(s) to exit\n", cnt);else if(vis[t.row][t.col])printf("%d step(s) before a loop of %d step(s)\n", step[t.row][t.col], cnt - step[t.row][t.col]);else {vis[t.row][t.col] = true;step[t.row][t.col] = cnt;if(maze[t.row][t.col] == 'S') q.push(Node(t.row + 1, t.col));if(maze[t.row][t.col] == 'N') q.push(Node(t.row - 1, t.col));if(maze[t.row][t.col] == 'E') q.push(Node(t.row, t.col + 1));if(maze[t.row][t.col] == 'W') q.push(Node(t.row, t.col - 1));}}
}int main()
{while(scanf("%d%d%d", &r, &c, &enter) && (r || c || enter)) {for(int i = 0; i < r; i++)scanf("%s", maze[i]);bfs();}return 0;
}

AC的C++语言程序(HDU,BFS)如下:

/* HDU1035 Robot Motion */#include <bits/stdc++.h>using namespace std;const int N = 10;
char maze[N][N + 1];
bool vis[N][N];
int step[N][N], r, c, enter, cnt;struct Node {int row, col;Node(int r = 0, int c = 0) : row(r), col(c) {}
};void bfs()
{memset(vis, false, sizeof(vis));step[0][enter - 1] = 0;queue<Node> q;q.push(Node(0, enter - 1));int cnt = -1;while(!q.empty()) {Node t = q.front();q.pop();cnt++;if(t.row < 0 || t.row >= r || t.col < 0 || t.col >= c)printf("%d step(s) to exit\n", cnt);else if(vis[t.row][t.col])printf("%d step(s) before a loop of %d step(s)\n", step[t.row][t.col], cnt - step[t.row][t.col]);else {vis[t.row][t.col] = true;step[t.row][t.col] = cnt;if(maze[t.row][t.col] == 'S') q.push(Node(t.row + 1, t.col));if(maze[t.row][t.col] == 'N') q.push(Node(t.row - 1, t.col));if(maze[t.row][t.col] == 'E') q.push(Node(t.row, t.col + 1));if(maze[t.row][t.col] == 'W') q.push(Node(t.row, t.col - 1));}}
}int main()
{while(scanf("%d%d", &r, &c) && (r || c)) {scanf("%d", &enter);for(int i = 0; i < r; i++)scanf("%s", maze[i]);bfs();}return 0;
}

这篇关于POJ1573 ZOJ1708 UVA10116 UVALive5334 HDU1035 Robot Motion【模拟】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/886354

相关文章

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

【算法专场】模拟(下)

目录 前言 38. 外观数列 算法分析 算法思路 算法代码 1419. 数青蛙 算法分析 算法思路 算法代码  2671. 频率跟踪器 算法分析 算法思路 算法代码 前言 在前面我们已经讲解了什么是模拟算法,这篇主要是讲解在leetcode上遇到的一些模拟题目~ 38. 外观数列 算法分析 这道题其实就是要将连续且相同的字符替换成字符重复的次数+

模拟实现vector中的常见接口

insert void insert(iterator pos, const T& x){if (_finish == _endofstorage){int n = pos - _start;size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);pos = _start + n;//防止迭代

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

1 模拟——67. 二进制求和

1 模拟 67. 二进制求和 给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。 示例 1:输入:a = "11", b = "1"输出:"100"示例 2:输入:a = "1010", b = "1011"输出:"10101" 算法设计 可以从低位到高位(从后向前)计算,用一个变量carry记录进位,如果有字符没处理完或者有进位,则循环处理。两个字符串对

AMAZING AUCTION(简单模拟)

AMAZING AUCTION 时间限制: 3000 ms  |  内存限制: 65535 KB 难度:4 描述 Recently the auction house hasintroduced a new type of auction, the lowest price auction. In this new system,people compete for the lo