Algorithm
Problem link- https://www.spoj.com/problems/TRGRID/
TRGRID - Traversing Grid
Starting at the top left corner of an N*M grid and facing towards the right, you keep walking one square at a time in the direction you are facing. If you reach the boundary of the grid or if the next square you are about to visit has already been visited, you turn right. You stop when all the squares in the grid have been visited. What direction will you be facing when you stop?
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
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
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.
Example
Input: 4 1 1 2 2 3 1 3 3 Output: R L D R
Constraints
1 <= T <= 10000
1 <= N, M <= 1000000000
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define MOD (ll)1000000007
#define pb push_back
#define EPS 1e-9
#define FOR(i,n) for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a;i <= b; i++)
#define pi(a) printf("%d\n", a)
#define all(c) c.begin(), c.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
#define sdi(a, b) si(a);si(b)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
#define F first
#define S second
#define FILL(arr, val) memset(arr, val, sizeof(arr))
#define read(arr, n) for(int i = 0;i < n; i++)cin>>arr[i];
#define sp ' '
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
int main(){
io;
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
if(n <= m){
if(n&1)
cout << "R" << endl;
else
cout << "L" << endl;
}else{
if(m&1>
cout << "D" << endl;
else
cout << "U" << endl;
}
}
return 0;
}Input
1 1
2 2
3 1
3 3
Output
L
D
R
Demonstration
SPOJ Solution-Traversing Grid-Solution in C, C++, Java, Python