My Advent of Code 2023 day 23 solution

AoC_day23_part1.cpp

// WARNING: Has thrown a stack overflow on debug, give it a big stack!
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
ifstream fin("a.txt");
int tiles[200][200];
int lines, cols;
int startx, endx;
int reachedin = 0;
int rchd[200][200];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
struct pos {
	int x, y;
};
bool vised[200][200];
void dfs(int x, int y, int nsteps) {
	if (x == endx && y == lines - 1) {
		reachedin = max(reachedin, nsteps);
		return;
	}
	if (x < 0 || y < 0 || x >= cols || y >= lines)
		return;
	if (tiles[y][x] == '#')
		return;
	if (rchd[y][x] >= nsteps)
		return;
	if (vised[y][x])
		return;
	vised[y][x] = 1;
	//cout << "dfs(" << x << ',' << y << ',' << nsteps << ")\n";
	rchd[y][x] = nsteps;

	int nx, ny;
	switch (tiles[y][x]) {
	case '.':
		for (int i = 0; i < 4; i++) {
			nx = x + dx[i];
			ny = y + dy[i];
			dfs(nx, ny, nsteps + 1);
		}
		break;
	case '>':
		nx = x + dx[0];
		ny = y + dy[0];
		dfs(nx, ny, nsteps + 1);
		break;
	case 'v':
		nx = x + dx[1];
		ny = y + dy[1];
		dfs(nx, ny, nsteps + 1);
		break;
	case '<':
		nx = x + dx[2];
		ny = y + dy[2];
		dfs(nx, ny, nsteps + 1);
		break;
	case '^':
		nx = x + dx[3];
		ny = y + dy[3];
		dfs(nx, ny, nsteps + 1);
		break;
	}

	vised[y][x] = 0;
}
void solve() {
	rchd[0][startx] = -1;
	dfs(startx, 0, 0);
	cout << reachedin;
}
void addline(const string& s) {
	if (!cols)
		cols = s.size();
	for (int i = 0; i < cols; i++) {
		tiles[lines][i] = s[i];
	}
	lines++;
}
int main() {
	string s;
	while (getline(fin, s)) {
		addline(s);
	}
	for (int i = 0; i < cols; i++) {
		if (tiles[0][i] == '.')
			startx = i;
		if (tiles[lines - 1][i] == '.')
			endx = i;
	}
	solve();
}

AoC_day23_part2.cpp

// WARNING: This is literal brute force and not the correct solution. With this, after
// many attempts (:<) I reached #109 on part 2.
// After 800,000 attempts I got the correct answer, note that 'down' is prioritized.
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
ifstream fin("a.txt");
int tiles[200][200];
int lines, cols;
int startx, endx;
int reachedin = 0;
int rchd[200][200];
int dx[] = { 0,1,-1,0 };
int dy[] = { 1,0,0,-1 };
struct pos {
	int x, y;
};
bool vised[200][200];
int reachedincounter;
void dfs(int x, int y, int nsteps) {
	if (x == endx && y == lines - 1) {
		if (reachedincounter++ > 1000000) { // increase if you aren't hitting the right answer\
			//cout << "Reached In " << reachedin << endl;
			exit(0);
		}
		if (reachedin >= nsteps)
			return;
		cout << "\rreached in " << nsteps;
		reachedin = max(reachedin, nsteps);
		return;
	}
	if (x < 0 || y < 0 || x >= cols || y >= lines)
		return;
	if (tiles[y][x] == '#')
		return;
	if (vised[y][x])
		return;

	vised[y][x] = 1;

	int nx, ny;
	for (int i = 0; i < 4; i++) {
		nx = x + dx[i];
		ny = y + dy[i];
		dfs(nx, ny, nsteps + 1);
	}
	
	vised[y][x] = 0;
}
void solve() {
	rchd[0][startx] = -1;
	dfs(startx, 0, 0);
	cout << reachedin;
}
void addline(const string& s) {
	if (!cols)
		cols = s.size();
	for (int i = 0; i < cols; i++) {
		tiles[lines][i] = s[i];
	}
	lines++;
}
int main() {
	string s;
	while (getline(fin, s)) {
		addline(s);
	}
	for (int i = 0; i < cols; i++) {
		if (tiles[0][i] == '.')
			startx = i;
		if (tiles[lines - 1][i] == '.')
			endx = i;
	}
	solve();
}