Fox Ciel is now in high school. The seats in her classroom are arranged into an n by m matrix. The rows are numbered from 0 to n-1 (front to back) and the columns from 0 to m-1 (left to right). At the beginning, Ciel can choose any of the seats. Then, at the end of each week Ciel will shift one row to the back and one column to the right, wrappi…

FoxAndClassroom.java

public class FoxAndClassroom {
	public static String ableTo(int m, int n){
		HashSet<Point> overallVisited=new HashSet<Point>();
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				Point cur=new Point(i,j);
				if(!overallVisited.contains(cur)){
					HashSet<Point> visited=new HashSet<Point>();
					while(!visited.contains(cur) && visited.size() < m*n){
						visited.add(cur);
						cur=next(cur,m,n);
					}
					if(visited.size() == m*n){
						return "Possible";
					}
					overallVisited.addAll(visited);
				}
			}
		}
		return "Impossible";
	}
	public static String ableTo_slow(int m, int n){
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				Point cur=new Point(i,j);
				HashSet<Point> visited=new HashSet<Point>();
				while(!visited.contains(cur) && visited.size() < m*n){
					visited.add(cur);
					cur=next(cur,m,n);
				}
				if(visited.size() == m*n){
					return "Possible";
				}
			}
		}
		return "Impossible";
	}
	private static Point next(Point cur, int m, int n){
		return new Point((cur.x+1)%m,(cur.y+1)%n);
	}
}

FoxAndClassroomTest.java

public class FoxAndClassroomTest {
	@Test
	public void testAbleTo() {
		assertEquals("Possible", FoxAndClassroom.ableTo(2, 3));
		assertEquals("Impossible", FoxAndClassroom.ableTo(2, 2));
		assertEquals("Impossible", FoxAndClassroom.ableTo(4, 6));
		assertEquals("Impossible", FoxAndClassroom.ableTo(3, 6));
	}
}