首页 / 软件开发 / 数据结构与算法 / COJ：Traversing Grid 遍历格子的问题 题解

COJ：Traversing Grid 遍历格子的问题 题解2015-02-25很有趣的题目：在一个方格上从最左上角面向右出发，每次行走一个，碰到边右走，或者碰到已经访问过的格子右转，问最后遍历所有格子的时候你是面向那个方向？

For example: Consider the case with N = 3, M = 3. The path followed will be （0,0） -> （0,1） -> （0,2） -> （1,2） -> （2,2） -> （2,1） -> （2,0） -> （1,0） -> （1,1）. At this point, all squares have been visited, and you are facing right.

Input specification

The first line contains T the number of test cases. Each of the next T lines contain two integers N and M, denoting the number of rows and columns respectively.

Output specification

Output T lines, one for each test case, containing the required direction you will be facing at the end. Output L for left, R for right, U for up, and D for down. 1 <= T <= 5000, 1 <= N,M <= 10^9.
Sample input

4
1 1
2 2
3 1
3 3

Sample output

R
L
D
R

一看题目好像很大的数据很难计算，不过其实是有规律的，并不用真的遍历所有格子。所以挺有趣的。

找出规律，几行代码就能通过了：

void TraversingGrid（）{int n = 0, m = 0, T = 0;cin>>T;while （T--）{cin>>n>>m;if （n <= m）{if （n % 2） cout<<"R"<<endl;else cout<<"L"<<endl;}else{if （m % 2） cout<<"D"<<endl;else cout<<"U"<<endl;}}}

出处：

http://coj.uci.cu/24h/problem.xhtml？abb=1004