2013
12-29

Mouse

A greedy mouse cici ate rat poison by mistake. To save herself, she have to drink.

Cici can only walk in four ways that marked in the photoes followed and only move in the region that colored blue..She expend energy every step.There are cheese in every position which cici can eat to gain energy once she is there.He will never reach the river if she run out of energy.The initially energy of cici is energy of the cheese at the coordinate (0,0).
if when the mouse arrive a position has 0 energy , he can’t eat the cheese.
Now can you help the wretched monse to calculate whether can he get to the river.
If she can,calculate the minimun energy of the maximal energy of every possible position of the river(Y = N-1).

There are several test cases.In each case,there are three integers n(0<n<=200),m(0<m<=10),and k(0<k<=10)in the first line ,the next n lines followed. The second line has only one integer c(0<c<=100),the i-th line has m integers more than (i-1)th line.
k is the energy each step cost.

There are several test cases.In each case,there are three integers n(0<n<=200),m(0<m<=10),and k(0<k<=10)in the first line ,the next n lines followed. The second line has only one integer c(0<c<=100),the i-th line has m integers more than (i-1)th line.
k is the energy each step cost.

7 2 3
5
3 6 4
6 9 2 5 6
2 5 3 7 1 6 7
8 9 3 2 6 3 8 9 5
3 5 3 6 4 3 5 6 8 4 2
2 6 3 3 6 7 8 5 3 1 4 5 6

11

Problem问题

A typical windowing system on a computer will provide a number of icons on the screen as well as some defined regions. When the mouse button is clicked, the system has to determine where the cursor is and what is being selected. For this problem we assume that a mouse click in (or on the border of) a region selects that region, otherwise it selects the closest visible icon (or icons in the case of a tie).

Consider the following screen:

A mouse click at ‘a’ will select region A. A mouse click at ‘b’ will select icon 1. A mouse click at ‘c’ will select icons 6 and 7. A mouse click at ‘d’ is ambiguous. The ambiguity is resolved by assuming that one region is in front of another. In the data files, later regions can be assumed to be in front of earlier regions. Since regions are labelled in order of appearance (see later) ‘d’ will select C. Note that regions always overlap icons so that obscured icons need not be considered and that the origin (0,0) is at the top left corner.

Write a program that will read in a series of region and icon definitions followed by a series of mouse clicks and return the selected items. Coordinates will be given as pairs of integers in the range 0..499 and you can assume that all icons and regions lie wholly within the screen. Your program must number all icons (even invisible ones) in the order of arrival starting from 1 and label regions alphabetically in the order of arrival starting from ‘A’.

Input输入

Input will consist of a series of lines. Each line will identify the type of data: I for icon, R for region and M for mouse click. There will be no separation between the specification part and the event part, however no icon or region specifications will follow the first mouse click. An I will be followed by the coordinates of the centre of the icon, R will be followed by the coordinates of the top left and bottom right corners respectively and M will be followed by the coordinates of the cursor at the time of the click. There will always be at least one visible icon and never more than 25 regions and 50 icons. The entire file will be terminated by a line consisting of a single #.

Output输出

Output will consist of one line for each mouse click, containing the selection(s) for that click. Regions will be identified by their single character identifier, icon numbers will be written out right justified in a field of width 3, and where there is more than one icon number they will appear in increasing numerical order.

Sample input输入示例

I       216     28
R       22      19      170     102
I       40      150
I       96      138
I       36      193
R       305     13      425     103
I       191     184
I       387     200
R       266     63      370     140
I       419     134
I       170     102
M       50      50
M       236     30
M       403     167
M       330     83
#

A
1
6  7
C

Solution解答

#include <iomanip>
#include <iostream>
#include <iterator>
#include <deque>
using namespace std;
struct POINT {int x; int y;};
struct RECT {POINT tl; POINT br;};
//判断点是否在矩形内
bool PointInRect(const POINT &pt, const RECT &rc) {
return (pt.x >= rc.tl.x && pt.x <= rc.br.x &&
pt.y >= rc.tl.y && pt.y <= rc.br.y);
}
//计算两点计距离的平方
int PointDistance(const POINT &pt1, const POINT &pt2) {
POINT Vec = {pt2.x - pt1.x, pt2.y - pt1.y};
return (Vec.x * Vec.x + Vec.y * Vec.y);
}
//主函数
int main(void) {
deque<POINT> Icons, Clicks;
deque<RECT> Rects;
//循环读入每一组数据
for (char Tag = 0; cin >> Tag && Tag != '#'; ) {
RECT rc;
switch (Tag) {
case 'I': //输入图标数据
cin >> rc.tl.x >> rc.tl.y;
Icons.push_back(rc.tl);
break;
case 'R': //输入矩形数据
cin >> rc.tl.x >> rc.tl.y >> rc.br.x >> rc.br.y;
if (rc.br.x < rc.tl.x) *(int*)0 = 0;
if (rc.br.y < rc.tl.y) *(int*)0 = 0;
Rects.push_back(rc);
if (Rects.size() > 26) *(int*)0 = 0;
break;
case 'M': //输入鼠标点击事件(坐标)
cin >> rc.tl.x >> rc.tl.y;
Clicks.push_back(rc.tl);
break;
}
}
deque<POINT>::iterator iIcon, iClick;
deque<RECT>::iterator iRect;
//检查是否存在图标被矩形覆盖
for (iIcon = Icons.begin(); iIcon != Icons.end(); ++iIcon) {
for (iRect = Rects.begin(); iRect != Rects.end(); ++iRect) {
if (PointInRect(*iIcon, *iRect)) {
iIcon->x = 10000; //将该图标移至无穷远处，即将其忽略
iIcon->y = 10000; //不能删除，以免影响后面图标的编号
}
}
}
//处理每一次鼠标点击事件
for (iClick = Clicks.begin(); iClick != Clicks.end(); ++iClick) {
//按题目要求，从后向前检查是否点在某个矩形内
deque<RECT>::reverse_iterator riRect;
for (riRect = Rects.rbegin(); riRect != Rects.rend() &&
!PointInRect(*iClick, *riRect); ++riRect);
//如果找到点在某个矩型，输出该矩形
if (riRect != Rects.rend()) {
cout << (char)(distance(riRect, Rects.rend()) - 1 + 'A') << endl;
continue;
}
//查找离鼠标位置距离最近的图标，存到动态数组SelIcons中
deque<int> SelIcons(1, 1);
deque<POINT>::iterator iNear = Icons.begin(), iIcon;
int nNear = PointDistance(*iClick, *iNear);
for (iIcon = iNear + 1; iIcon != Icons.end(); ++iIcon) {
int nDist = PointDistance(*iClick, *iIcon); //计算距离
if (nDist < nNear) {
iNear = iIcon;
nNear = nDist;
SelIcons.clear(); //清空原先的数组，以新图标代替
SelIcons.push_back(distance(Icons.begin(), iIcon) + 1);
}
else if (nDist == nNear) { //发现同为最短距离的图标则加入数组
SelIcons.push_back(distance(Icons.begin(), iIcon) + 1);
}
}
//按要求的格式输出图标的编号
deque<int>::iterator iSel;
for (iSel = SelIcons.begin(); iSel != SelIcons.end(); ++iSel) {
cout << setw(3) << *iSel;
}
cout << endl;
}
return 0;
}

1. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}

2. This write-up presents the gentle in which we can notice the fact. this is extremely wonderful one and gives in depth info.