Submission #503533

#	Time	Username	Problem	Language	Result	Execution time	Memory
503533		brayden04	Trampoline (info1cup20_trampoline)	C++14	23 / 100	1810 ms	20280 KiB

trampoline

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

int R, C, N = 0;

bool trampolines[4005][4005];
bool visited[4005][4005];

int xStart = 0;
int yStart = 0;
int xEnd = 0;
int yEnd = 0;

bool dfs(int x, int y){
  if (visited[x][y] == true) return false;
  if (x > R || x < 1 || y > C || y < 1) return false;
  visited[x][y] = true;

  if (x == xEnd && y == yEnd){
    return true;
  }

  if (trampolines[x][y] == false){
    if (visited[x][y + 1] == false){
      dfs(x, y+1);
    }
  }
  else{
    if (visited[x + 1][y] == false){
      dfs(x + 1, y);
    }
    if (visited[x][y + 1] == false){
      dfs(x, y+1);
    }
  }
  return visited[xEnd][yEnd];
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  memset(trampolines, false, sizeof(trampolines[0][0])*2500*2500);
  cin >> R >> C >> N;

  for (int i = 0; i < N; i++){
    int temp1 = 0;
    int temp2 = 0;
    cin >> temp1 >> temp2;
    trampolines[temp1][temp2] = true;
  }

  int T = 0;
  cin >> T;

  for (int i = 0; i < T; i++){
    memset(visited, false, sizeof(visited[0][0])*2500*2500);

    cin >> xStart >> yStart >> xEnd >> yEnd;

    bool test = dfs(xStart, yStart);

    if (test){
      cout << "Yes" << endl;
    }
    else{
      cout << "No" << endl;
    }
  }
}

• Subtask 1: 23 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 27