Problem 2217 : Let's JUMPSTYLE

AOJ 探索

問題概要

日本語なので本文参照（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2217&lang=jp）

解法

深さ優先探索によって解ける。
ジャンプして、

  • 行き先がすでに判明したループだったら、今までの道にそのループの番号を入れる
  • 行き先が現在の道につながってしまったら、このループに新たな番号をつけ、今までの道にこの番号を入れる

のような関数を書けばよい。
全てのマスに対してこの関数を適用し、終了時のループの番号が答えとなる。

ソースコード

int n,x[100][100],y[100][100];
int v[100][100],nv;

int rec(int cy,int cx)
{
	int &c=v[cy][cx];
	if(c==-2)return nv++,-2;
	if(c>=0)return c;
	c=-2;
	
	int ny=y[cy][cx],nx=x[cy][cx],r=rec(ny,nx);
	c=r==-2?nv-1:r;
	return r;
}

int main()
{
	while(scanf("%d",&n),n)
	{
		rep(i,n)rep(j,n)scanf("%d%d",x[i]+j,y[i]+j),v[i][j]=-1;
		nv=0;
		rep(i,n)rep(j,n)if(v[i][j]<0)rec(i,j);
		printf("%d\n",nv);
	}
	return 0;
}