joyの過去問

[Ｃｒ]

Ｃｒです。
joyの過去問のこれhttp://www.ioi-jp.org/joi/2010/2011-yo-prob_an ... .htmlなんですが…
問題を簡単に説明すると、迷路を解く問題で
X：壁(通れない)
.：通路(通れる)
S:スタート地点
数字:1から順番に通ること
という制約で最短で数字を全部通れという問題です
一行目は迷路の縦　横　数字の数
二行目から迷路の情報が与えられます。
入力サンプルはこんな感じです

コード:

4 5 2
.X..1
....X
.XX.S
.2.X.

コード:

#include <cstdio>
#include <cstdlib>
#include <set>
using namespace std;

int solve(set<int>now1,set<int>*now2,set<int>*root,int pow,char o[1000][1000],int a,int b){
//引数は順に、今いる地点の集合、次の地点を格納するためのポインタ、今まで通った道を格納する集合、目的地の数字、迷路の大元、迷路の縦、横の大きさ
	set<int>::iterator it;

	(*now2).clear();
//最初にnow2に入ってる値を消す
	while(!now1.empty()){	//今いる地点の処理がすべて終わるまで
		it = now1.begin();	//今いる地点のうち一つをitに入れる
		
		if( *it -b >= 0 && (*root).find( *it - b ) == (*root).end() ){　
						//上が座標として存在するか、その座標がまだ通ってないか
			if(o[*it/b-1][*it%b]!='S'&&o[*it/b-1][*it%b]!='X'&&o[*it/b-1][*it%b]!=pow){
						//それが通れる道か
				(*now2).insert(*it-b);	//次の道と通った道にその地点を格納
				(*root).insert(*it-b);
			}else if(o[*it/b-1][*it%b]==pow){
						//座標が目的地なら
				(*root).clear();
				(*now2).clear();
			//それぞれ一回全部消した後、次のスタート地点となるさっきまでの目的地を格納
				(*root).insert(*it-b);
				(*now2).insert(*it-b);
				return 1;
			}
		}

		if( *it+b < b*b && (*root).find( *it + b ) == (*root).end() ){//下で同じことをやる
			if(o[*it/b+1][*it%b]!='S'&&o[*it/b+1][*it%b]!='X'&&o[*it/b+1][*it%b]!=pow){
				(*now2).insert(*it+b);
				(*root).insert(*it+b);
			}else if(o[*it/b+1][*it%b]==pow){
				(*root).clear();
				(*now2).clear();
				(*root).insert(*it+b);
				(*now2).insert(*it+b);
				return 1;
			}
		}

		if( *it%b != 0 && (*root).find( *it - 1 ) == (*root).end() ){//左で同じことを
			if(o[*it/b][*it%b-1]!='S'&&o[*it/b][*it%b-1]!='X'&&o[*it/b][*it%b-1]!=pow){
				(*now2).insert(*it-1);
				(*root).insert(*it-1);
			}else if(o[*it/b][*it%b-1]==pow){
				(*root).clear();
				(*now2).clear();
				(*root).insert(*it-1);
				(*now2).insert(*it-1);
				return 1;
			}
		}

		if( *it%b != b-1 && (*root).find( *it +1 ) == (*root).end() ){//右で同じことを
			if(o[*it/b][*it%b+1]!='S'&&o[*it/b][*it%b+1]!='X'&&o[*it/b][*it%b+1]!=pow){
				(*now2).insert(*it+1);
				(*root).insert(*it+1);
			}else if(o[*it/b][*it%b+1]==pow){
				(*root).clear();
				(*now2).clear();
				(*root).insert(*it+1);
				(*now2).insert(*it+1);
				return 1;
			}
		}
		
		
		now1.erase(it++);//itは確認したので集合から削除　次の処理へ
		
	}
	return 0;//目的地に到達できなかったら0を返す
}

int main(void){
	int a,b;				//迷路の縦と横
	int n;					//通る数字の数
	int i,j;				//最初にＳの位置を見つける用
	int pow = 1+48;			//数字の比較用
	int ans = 0;			//答えを入力
	int check;				//solve()が数字を見つけたかの判定
	char o[1000][1000]={0};	//迷路の大元
	/************
	*　　　読みとり　　 *
	************/
	scanf("%d %d %d",&a,&b,&n);	//一行目読み取り

	for(int i=0 ;i<a ;i++){
		scanf("%*c");			//改行の読み飛ばし
		for( int j=0; j<b; j++){
			scanf("%c",&o[i][j]);	//迷路の読み取り
		}
	}

	set<int> root;			//一度通った点を記録
	set<int> now1;			//今の歩数で立つことができる点のうち、まだ通ってない点

						//平面座標を格納するのでx座標×横幅+y座標で整数として格納

	for(i=0;i<a;i++){
		for(j=0;j<b;j++){
			if(o[i][j]==83){			//Sを探す　見つかったらループ脱出
				goto KOKODAKEHA;	//gotoの誘惑に負けました
			}
		}
	}
	KOKODAKEHA:
	root.insert(i*b+j);		//rootとnow1にSを格納
	now1.insert(i*b+j);

	for(;pow <= n+48;){		//全ての点を通るまで
		check = solve(now1,&now1,&root,pow,o,a,b);	//solveで次にいける道をnow1に格納
		ans++;								//答えの距離を1増やす
		if(check<=0){							//帰り値が0以下ならまだ数字に達してない
#ifdef DEBUG
			printf("%d\n",ans);
#endif
		}else if(check>0){						//帰り値が0より大きければ数字に達した
			pow++;							//次の目的地へ　数字を1増やす
		}
	}

	printf("%d",ans);		//終わったら答えを返す
	return 0;

}

入力に対して答えが違うのですが、どこが間違っているのか分かりません
http://www.ioi-jp.org/joi/2010/2011-yo- ... o-t5.htmlの
入力2に対して284を返すところを274を返してしまい
入力3はあってましたが
入力4,5に至っては答えが出てこずループが終わりません…
入力3は縦と横の大きさが一緒なのでそれが原因か？とか思ったのですがイマイチ原因が分かりません
分かる方お願いします。

[xxx]

joyではなくJOIです.
15行目に全角空白が入っています.

コード:

1 5 3
3S21.

の場合は7です.('S'は何度でも通ることができます.

なぜ'0'と書かずに48と書くのか'S'を83と書くのかかなり気になりますがバグの要因にしかならないのでやめたほうがいいです.

座標を1変数に押しこむのは嫌いなので読んでませんが適当に変えたら正しい解が出ました.
おそらく座標の遷移ミスだと思うので確認してみてください.

コード:

int solve(set<int>now1,set<int>*now2,set<int>*root,int pow,char o[1000][1000],int a,int b){
  //引数は順に、今いる地点の集合、次の地点を格納するためのポインタ、今まで通った道を格納する集合、目的地の数字、迷路の大元、迷路の縦、横の大きさ
  set<int>::iterator it;
 
  (*now2).clear();
  //最初にnow2に入ってる値を消す
  while(!now1.empty()){   //今いる地点の処理がすべて終わるまで
    it = now1.begin();  //今いる地点のうち一つをitに入れる
    if(*it<0)continue;
    static int dx[]={1,0,-1,0};
    static int dy[]={0,1,0,-1};
    for(int i=0;i<4;i++){
      int x=*it%b+dx[i];
      int y=*it/b+dy[i];
      if(x<0 || x>=b || y<0 || y>=a || o[y][x]=='X') continue;
      if(o[y][x]==pow){
        (*root).clear();
        (*now2).clear();
        (*root).insert(y*b+x);
        (*now2).insert(y*b+x);
        return 1;
      } else {
        (*now2).insert(y*b+x);
        (*root).insert(y*b+x);
      }
    }
    now1.erase(it++);//itは確認したので集合から削除　次の処理へ
        
  }
  return 0;//目的地に到達できなかったら0を返す
}

>入力4,5に至っては答えが出てこずループが終わりません…
このプログラムのオーダー(計算量)はいくつになるか見積もれますか？

[Ｃｒ]

roxion1377 さん、回答ありがとうございます
S何度でも通れるんですよね…
なんで除外したんだろう…
今日プログラムを印刷して一日眺めてたところ、32行目の下へ行く判定でa*b(縦×横　要するに一番大きな座標)より小さいってしなきゃダメなところをb*bになってるのが原因の一つでしたorz
にしても、すごくきれいなプログラミングで、脱帽です

オーダーですか…
一応名前ぐらいは知ってますが、詳しくは知らないです。
普通の計算は一瞬でコンピューターは処理できるから繰り返しの部分にどれだけ時間がかかるかをO(n^2)とかであらわす…だったような……

一回通った点は除外されるから、最大でも1000*1000*9回のループ？
スミマセン良く分かんないです。

[Ｃｒ]

Sと32行目のb*bを直したところ
とりあえず、問題は解けるようになりました。
(答えは出るという意味で)
時間としては、いちばん解答の値が大きい657150で、問題を読み込むのに16秒、解答を出すまでに15秒かかりました。
これはプログラミングコンテスト的にはアウトですか？

[xxx]

>一回通った点は除外されるから、最大でも1000*1000*9回のループ？
そうですね.
しかしstd::setを使っているのでO( (H*W*log2(H*W))*N )になります.

>時間としては、いちばん解答の値が大きい657150で、問題を読み込むのに16秒、解答を出すまでに15秒かかりました。
>これはプログラミングコンテスト的にはアウトですか？
最適化をかければ3sほどで終わりますし答えもあっているので問題ないと思います.
時間がかかりすぎるのはJOIの予選では答えが出れば良いのでOKですが本選などではダメです.

[Ｃｒ]

いろいろと有意義な情報ありがとうございます。
予選は答えが出ればいいんですね…
初めて知りました
とりあえず、正確な答えが求められるようになったので解決としたいと思います。
roxion1377 さん、どうもありがとうございました。