yukicoder : No.1647 Travel in Mitaru city 2

ミタルって何か元ネタがあるのかな。
https://yukicoder.me/problems/no/1647

問題

グリッド上いくつかのマスに観光名所がある。
以下のような観光名所の列があればそれを答えよ。

• 任意の観光名所で開始し、同じ場所で終了する。
• 奇数回目の移動では、同じ行の観光名所に移動する。(途中同じ行にある他の観光名所を通過してもよい)
• 偶数回目の移動では、同じ列の観光名所に移動する。(途中同じ列にある他の観光名所を通過してもよい)

解法

縦横交互に移動する、という条件の下でDFSしながら閉路を検出しよう。

int H,W,N;
int X[202020],Y[202020];

vector<pair<int,int>> E[402020];
vector<pair<int,int>> path;
int vis[404040];

void dfs(int cur,int pre) {
	
	if(vis[cur]) {
		vector<int> ret;
		int ok=0;
		FORR2(e,i,path) {
			if(ok) ret.push_back(i+1);
			if(e==cur) ok++;
		}
		if(cur>=H) {
			reverse(ret.begin(),ret.end()-1);
		}
		
		cout<<ret.size()<<endl;
		FORR(r,ret) cout<<r<<" ";
		cout<<endl;
		exit(0);
		
	}
	vis[cur]=1;
	FORR2(e,i,E[cur]) if(e!=pre) {
		path.push_back({e,i});
		dfs(e,cur);
		path.pop_back();
		
	}
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>N;
	FOR(i,N) {
		cin>>Y[i]>>X[i];
		Y[i]--,X[i]--;
		E[Y[i]].push_back({H+X[i],i});
		E[H+X[i]].push_back({Y[i],i});
	}
	
	FOR(y,H) if(vis[y]==0) {
		path.push_back({y,-1});
		dfs(y,-1);
		path.pop_back();
	}
	
	cout<<-1<<endl;
	
}

まとめ

難しくはないけど、なんか妙にWAを重ねてしまった。