AOJ : 2217 - Let's JUMPSTYLE

AOJ 実装問題

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2217&lang=jp
日本語なので省略です

アルゴリズム

  • 今ままで通った地点を記憶できるような二次元配列loopを作っておきます
  • loopの全要素を0で初期化
  • loopの配列を左上から調べて, 今までにたどったことがない場所(0である)なら, そこからジャンプし始める
    • 自分がたどったところに印をつけつつ進む
    • 現在行っているループに行き着いたら, ループとして数える.
    • 前回までに行ったループに行き着いたら, それはループとして数えない

説明わかりづらいです.
すみません.

プログラム

#include <iostream>
#include <cstring>
using namespace std;

typedef pair<int,int> P;

P t[101][101];
int loop[101][101];

int solve(int x,int y,int now){
  while(loop[y][x] == 0){
    loop[y][x] = now;
    int nx = t[y][x].first;
    int ny = t[y][x].second;
    x = nx;
    y = ny;
  }

  if(loop[y][x] == now) return 1;
  return 0;
}

int main(void){
  int n;

  while(cin>>n && n){
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        cin>>t[i][j].first>>t[i][j].second;
      }
    }

    memset(loop,0,sizeof(loop));
    int now = 1;
    int ans = 0;

    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        if(loop[i][j] == 0){
          ans += solve(j,i,now);
          now++;
        }
      }
    }

    cout<<ans<<endl;
  }

  return 0;
}