Блог пользователя Jellyman102

An Efficient (and quite common) Way to Navigate Grid Problems [C++]
Автор Jellyman102, 4 года назад, По-английски

Although a lot of people do this, I wanted to write a blog about how the following line of template code can help when solving a problem involving BFS on a grid or iterating over adjacent cells.

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

The way this works is quite simple. First, create a for loop like this:

for(int i = 0; i < 4; i++){

Then, using the x and y of the current cell, store the coordinates of the adjacent cell in newX and newY (or however you want to name your variables).

newX = x + dx[i]; newY = y + dy[i];

Now you can do whatever you need to do with newX and newY within the for loop (whether it's pushing to a queue for BFS or running some conditional). Make sure you check for out of bounds (which can be done with the function below).

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

I know this is quite basic and a very common tactic, but I felt the need to write this to serve as an introduction to this technique for newer CPers. Hopefully this will save somebody lots of time. Feel free to share your techniques with grid problems in the comments.

Stay Safe! — Jellyman

NOTE: This is my first blog. Sorry if the formatting is garbage.

EDIT: Here is my solution to a problem I solved in a recent div 2 contest using this technique: 82826532

  • Проголосовать: нравится
  • +270
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +38 Проголосовать: не нравится

Is funny because this is well know but I did not see it anywhere except in someone else code when I was starting. Hope people see it now and don't waste time making a lot of if-else as I did.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Why and how does this work?

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    Sorry for the late reply. When i is 0, then newX becomes x + dx[0], which is x + 1. This means that when i is 0, newX and newY represent the cell to the right (y does not change because dy[0] is 0). Then, i becomes 1. When i is one, newX and newY represent the cell to the right, because newX = x + 0 and newY = y + 1. i = 2 and i = 3 checks left and bottom respectively. Hope this makes sense.

    → Ответить
»
4 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

For problems involving diagonal transitions as well (like, a king's move in chess), you can do the same thing:

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

So far, this is pretty obvious, but the cool part (at least, I find it kind of clever) is that in the situation with only 4 transitions, you can use the exact same code, and just loop over the first 4 elements.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Thanks for pointing this out!

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please explain how did you choose array dx and dy?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Write down the coordinates for the points in a 3x3 square around the origin, now put the x's and the y's in two separate arrays. I put the horizontal/vertical points before the diagonal ones, so that we can do the trick I mentioned.

      → Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
    or you can also do
    → Ответить
»
4 года назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

one suggestion: provide a link to any such grid problem and show the full code to demonstrate this method.

→ Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +59 Проголосовать: не нравится

With C++17 (or just GCC >= 8) it can be done in simpler way without indexing:

#include <bits/stdc++.h>
using pii = std::pair<int,int>;
const pii steps[] = {{-1,0},{1,0},{0,-1},{0,1}};
...
    for (auto [dx,dy] : steps) {
        int newX = x + dx;
        int newY = y + dy;
    }
...

Example

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I saw Errichto do it in floodfill problem, I also started doing it since then, pretty cool.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Surely your method is clean and nice. There is another way to navigate:
0 : Up 1 : Left 2 : Down 3 : Right

for(int d = 0; d < 4;  ++d) {
  new_row = row + (d == 2) - (d == 0);
  new_col = col + (d == 3) - (d == 1);
  // (new_row, new_col) is the immediate neighbor of (row, col) towards direction of d
}

I learned this in one of icecuber's solutions and I think it's pretty cool!

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
  1. 510B - Fox And Two Dots — 71727892
  2. 129C - Statues — 82305353
  3. 242C - King's Path — 68319687
  4. 378C - Maze — 79771511
  5. 1365D - Solve The Maze — 82886084 Some problems to try. Submissions for reference.
→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For people who uses vector instead of global C style array, there may be some problems that could get TLE if not used carefully: https://codeforces.net/blog/entry/77847

→ Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Also, you can use this to check if you are within the borders:

if(unsigned(x)<n&&unsigned(y)<m){
//do sth
}
→ Ответить
»
4 недели назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

You could also do:

// up, right, down, left
vector<int> d = {-1, 0, 1, 0, -1}

for(int i=0; i<4; i++)
newX = x + d[i]; newY = y + d[i+1];
→ Ответить
  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes this is also cool. To include the diagonal movements, we can use this code: 

    // up, right, down, left, top-left, top-right, bottom-right, bottom-left
vector<int> d = {-1, 0, 1, 0, -1, -1, 1, 1, -1}

for(int i=0; i<8; i++){
    newX = x + d[i]; newY = y + d[i+1];
    //rest of the code using these new coordinates.
}
    → Ответить