Iterating over the boundary of a grid

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Hello,

I was wondering if there's any trick that allows us to iterate over the boundary of an $$$N \times M$$$ grid using a single loop instead of 4 or 2.

To iterate over the whole grid for example we can iterate from 0 to $$$NM$$$ and have $$$i = x / M$$$ and $$$j = x \% M$$$.

So is there any smart thing like this to do for the boundary only (i.e pairs $$$(i, j)$$$ such that either $$$i = 0$$$ or $$$i = N - 1$$$ or $$$j = 0$$$ or $$$j = M - 1$$$)

Thanks for future help!

EDIT: Problem Solved!

Solution 1

Solution 2

Proposed by: bthero ~~~~~ bool inside(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }

int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0};

int x = 0, y = 0, d = 0;

do { // do stuff with (x, y)

if (!inside(x + dx[d], y + dy[d])) {
    d++;
}

x += dx[d];
y += dy[d];

} while (x != 0 || y != 0); ~~~~~

My Solution inspired by the previous one

for(int x = 0; x < n * m; x++) {
    int i = x / m, j = x % m;
    cout << i << ' ' << j << '\n';
    x += (m - 2) * (m != 1 && i != 0 && i != n - 1 && j == 0);
}

Комментарии (5)

Написать комментарий?

under_score_07

3 года назад, # |

← Rev. 2 →

Here you go

code

int x=0,y=1,i=0,j=0;
while(1)
{
    cout<<i<<" "<<j<<endl;
    if(x==0 and y==1)
    {
        if(j==m-1)
            x=1,y=0;
    }
    else if(x==1 and y==0)
    {
        if(i==n-1)
            x=0,y=-1;
    }
    else if(x==0 and y==-1)
    {
        if(j==0)
            x=-1,y=0;
    }
    i+=x,j+=y;
    if(i==0 and j==0)
        break;
    }
}

→ Ответить

0-jij-0

3 года назад, # ^ |

This is clever! Thank you for the suggestion

bthero

+25

I would probably do it this way:

bool inside(int x, int y) {
	return 0 <= x && x < n && 0 <= y && y < m;
}

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int x = 0, y = 0, d = 0;

do {
	// do stuff with (x, y)

	if (!inside(x + dx[d], y + dy[d])) {
		d++;
	}

	x += dx[d];
	y += dy[d];
}
while (x != 0 || y != 0);

But note that it doesn't work when $$$n = 1$$$ or $$$m = 1$$$ so you will probably have to run a simple loop for that.

← Rev. 3 →

I got your point and your idea to skip the stuff in between actually inspired me to get the following and the complexity would be simply $$$O(N + M)$$$

Code

Thank you!

Auto comment: topic has been updated by 0-jij-0 (previous revision, new revision, compare).

Блог пользователя 0-jij-0