JOI2010予選 問６のソースコード

ソースコード

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int w,h,n;
int kx,ky;
int map[20][20];
vector<pair<int,int> > pts;
vector<vector<int> > memo;


int findnext(int dir,int state,int x,int y)
{
	int dx=0,dy=0;
	if(dir==0){dy=-1;}
	if(dir==2){dy=1;}
	if(dir==1){dx=-1;}
	if(dir==3){dx=1;}
	x+=dx;y+=dy;
	while(0<=x&&x<w&&0<=y&&y<h)
	{
		if(map[x][y]>=0&&((state&1<<map[x][y])==0))
		{
			return map[x][y];
		}
		x+=dx;y+=dy;
	}
	return -1;
}

int calc(int state,int id)
{
	if(memo[state][id]>=0){return memo[state][id];}
	int x=pts[id].first;
	int y=pts[id].second;
	if(state == (1<<n)-1)
	{
		if(x==kx||y==ky){return 1;}
		else {return 0;}
	}
	int sum=0;
	int next=-1;
	if((next=findnext(0,state,x,y))!=-1){sum += calc(state|1<<next,next);}
	if((next=findnext(1,state,x,y))!=-1){sum += calc(state|1<<next,next);}
	if((next=findnext(2,state,x,y))!=-1){sum += calc(state|1<<next,next);}
	if((next=findnext(3,state,x,y))!=-1){sum += calc(state|1<<next,next);}
	memo[state][next]=sum;
	return sum;
}

int main()
{
	int tmp;
	scanf("%d %d",&w,&h);
	for(int j=0;j<h;j++)
	{
		for(int i=0;i<w;i++)
		{
			scanf("%d",&tmp);
			if(tmp==1)
			{
				map[i][j]=pts.size();
				pts.push_back(make_pair(i,j));
			}
			else
			{
				map[i][j]=-1;
				if(tmp==2){kx=i;ky=j;}
			}
		}
	}
	n=pts.size();
	memo = vector<vector<int> >(1<<n);
	for(int i=0;i<1<<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			memo[i].push_back(-1);
		}
	}
	int result=0;
	int next=-1;
	if((next=findnext(0,0,kx,ky))!=-1){result += calc(1<<next,next);}
	if((next=findnext(1,0,kx,ky))!=-1){result += calc(1<<next,next);}
	if((next=findnext(2,0,kx,ky))!=-1){result += calc(1<<next,next);}
	if((next=findnext(3,0,kx,ky))!=-1){result += calc(1<<next,next);}
	printf("%d\n",result);
}

入力データ１での実行結果

$ ./a.exe < in.txt
36
Aborted (core dumped)

これを読んだあなた。どうかAbortedの真相を暴いてください。それだけが私の望みです。

＊追記　02/18 22:28
calcの中のmemo[state][next]=sum;が間違っていました。
正しくはmemo[state][id]=sum;
いわゆるメモ化再帰です。…なんでAcceptedだったんだろう？