rt 本地测0.15s 到了CF上就T掉了

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 0721;
string s[N];
struct node {
	int x, y;
} q[N];
int dx[2] = {0, 1};
int dy[2] = {1, 0};
int top;
int n, m;
bool flag;

inline bool exist(int x, int y) {
	return x > 0 && x <= n && y >= 0 && y < m && s[x][y] != '#';
}

void dfs(int x, int y) {
	if (flag) return;
	for (int i = 0; i <= 1; ++i) {
		if (flag) return;
		int tox = x + dx[i], toy = y + dy[i];
//		cout<<tox<<" "<<toy<<'\n';
		if (!exist(tox, toy)) continue;
		if (tox == n && toy == m - 1) {
			flag = 1;
			return;
		}
		q[++top] = (node){tox, toy};
		dfs(tox, toy);
		if (flag) return;
		--top;
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) cin >> s[i];
	
	dfs(1, 0);
	if (!flag) {
		printf("0");
		return 0;
	}
	for (int i = 1; i <= top; ++i) {
		s[q[i].x][q[i].y] = '#';
	}
	flag = 0;
	top = 0;
	dfs(1, 0);
//	for (int i = 1; i <= top; ++i) cout << q[i].x << ' ' << q[i].y << '\n';
	if (flag) printf("2");
	else printf("1");
	
	return 0;
}