Internet Problem Solving Contest

IPSC 2017

Problem A – Automated flooding

You are playing a computer game in which your goal is to flood the whole world.

The world is an r × c rectangle divided into unit square cells. Currently, all cells are dry. The game has two separate phases:

Problem specification

You are given the dimensions of the world. Flood the entire world using as few clicks as possible.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of a single line with two positive integers r and c: the dimensions of the world. The individual cells of the world have coordinates ranging from (0, 0) to (r − 1, c − 1).

You may assume that t = 100 and that 1 ≤ r, c ≤ 100.

In the easy subproblem A1 you may also assume that r = c (i.e., the world is a square).

Output specification

For each test case output a block of lines. The first line of the block should contain the number x of clicks you should make. Each of the following x lines should contain the coordinates of a cell you should click. There are usually multiple optimal solutions. We will accept any of them.

What to submit

Do not submit any programs. Your task is to produce and submit the correct output files a1.out and a2.out for the provided input files a1.in and a2.in.




2 2

3 4


0 1
1 0
0 0
0 2
2 2
2 3

The second sample output is illustrated below, with ‘W’ denoting a water cell and ‘.’ denoting a dry cell. On the left is the state of the world just after you made the four clicks. Progressing towards the right you see how the water spreads until it floods the entire world.

        W.W.        WWW.        WWW.        WWWW        WWWW
        ....   ->   ..W.   ->   .WWW   ->   WWWW   ->   WWWW
        ..WW        ..WW        ..WW        .WWW        WWWW