AOJ 0508,0548,0581 - tozangezan's diary

ようやくVolume 5が全部埋まりました。まだ増えるだろうけど、せいぜい８個。

0508
枝かりゲーだと思っていたら枝かりの必要すらなかった。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>g[100];
int used[100];
int solve(int a){
	used[a]=1;
	int ret=1;
	for(int i=0;i<g[a].size();i++){
		if(!used[g[a][i]]){
			ret=max(ret,1+solve(g[a][i]));
		}
	}
	used[a]=0;
	return ret;
}
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<100;i++)g[i].clear();
		for(int i=0;i<a;i++){
			int b,c;
			scanf("%d%d",&b,&c);
			b--;c--;
			g[b].push_back(c);
			g[c].push_back(b);
		}
		int ret=0;
		for(int i=0;i<100;i++)ret=max(ret,solve(i));
		printf("%d\n",ret);
	}
}

0548
逆から探索すると速い。これも枝かりいらなかった。

#include<stdio.h>
#include<algorithm>
using namespace std;
int m[10][10];
int R;
int C;
int a,b;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int solve(int s,int t,int u){
	if(u==0){
		if(s==R||t==C)return 1;
		else return 0;
	}
	int ret=0;
	for(int i=0;i<4;i++){
		int row=s;
		int col=t;
		while(1){
			row+=dx[i];
			col+=dy[i];
			if(row<0||col<0||row>=a||col>=b)break;
			if(m[row][col]==1){
				m[row][col]=3;
				ret+=solve(row,col,u-1);
				m[row][col]=1;
				break;
			}
		}
	}
	return ret;
}
int main(){
	while(scanf("%d%d",&b,&a),a){
		int c=0;
		for(int i=0;i<a;i++)
			for(int j=0;j<b;j++){
				scanf("%d",&m[i][j]);
				if(m[i][j]==1)c++;
				if(m[i][j]==2){R=i;C=j;}
			}
		printf("%d\n",solve(R,C,c));
	}
}

0581
のDP。配列の次元だけ増えるつまらない問題。

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[50][50][1<<12][4];
char str[50][51];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++)scanf("%s",str[i]);
	for(int i=0;i<a;i++)
		for(int j=0;j<b;j++)
			if(str[i][j]=='.')str[i][j]='0';
	for(int i=0;i<a;i++)
		for(int j=0;j<b;j++)
			for(int k=0;k<(1<<12);k++)
				for(int l=0;l<4;l++)
					dp[i][j][k][l]=-99999999;
	dp[0][0][0][c]=0;
	for(int i=c;i>=0;i--){
		for(int j=0;j<a;j++){
			for(int k=0;k<b;k++){
				for(int l=0;l<(1<<12);l++){
					if(dp[j][k][l][i]<0)continue;
					int R;
					int W;
					bool ok;
					if(j<a-1&&str[j+1][k]!='#'){
						R=0;W=0;ok=true;
						for(int m=0;m<6;m++){
							R-=dx[(l>>(m*2))&3];
							W-=dy[(l>>(m*2))&3];
							if(R==1&&W==0)ok=false;
						}
						if(ok){
							dp[j+1][k][(l<<2)&((1<<12)-1)][i]=max(dp[j][k][l][i]+str[j+1][k]-'0',dp[j+1][k][(l<<2)&((1<<12)-1)][i]);
						}else{
							dp[j+1][k][(l<<2)&((1<<12)-1)][i]=max(dp[j][k][l][i],dp[j+1][k][(l<<2)&((1<<12)-1)][i]);
						}
					}
					if(k<b-1&&str[j][k+1]!='#'){
						R=0;W=0;ok=true;
						for(int m=0;m<6;m++){
							R-=dx[(l>>(m*2))&3];
							W-=dy[(l>>(m*2))&3];
							if(R==0&&W==1)ok=false;
						}
						if(ok){
							dp[j][k+1][((l<<2)+1)&((1<<12)-1)][i]=max(dp[j][k][l][i]+str[j][k+1]-'0',dp[j][k+1][((l<<2)+1)&((1<<12)-1)][i]);
						}else{
							dp[j][k+1][((l<<2)+1)&((1<<12)-1)][i]=max(dp[j][k][l][i],dp[j][k+1][((l<<2)+1)&((1<<12)-1)][i]);
						}
					}
					if(j&&str[j-1][k]!='#'&&i){
						R=0;W=0;ok=true;
						for(int m=0;m<6;m++){
							R-=dx[(l>>(m*2))&3];
							W-=dy[(l>>(m*2))&3];
							if(R==-1&&W==0)ok=false;
						}
						if(ok){
							dp[j-1][k][((l<<2)+2)&((1<<12)-1)][i-1]=max(dp[j][k][l][i]+str[j-1][k]-'0',dp[j-1][k][((l<<2)+2)&((1<<12)-1)][i-1]);
						}else{
							dp[j-1][k][((l<<2)+2)&((1<<12)-1)][i-1]=max(dp[j][k][l][i],dp[j-1][k][((l<<2)+2)&((1<<12)-1)][i-1]);
						}
					}
					if(k&&str[j][k-1]!='#'&&i){
						R=0;W=0;ok=true;
						for(int m=0;m<6;m++){
							R-=dx[(l>>(m*2))&3];
							W-=dy[(l>>(m*2))&3];
							if(R==0&&W==-1)ok=false;
						}
						if(ok){
							dp[j][k-1][((l<<2)+3)&((1<<12)-1)][i-1]=max(dp[j][k][l][i]+str[j][k-1]-'0',dp[j][k-1][((l<<2)+3)&((1<<12)-1)][i-1]);
						}else{
							dp[j][k-1][((l<<2)+3)&((1<<12)-1)][i-1]=max(dp[j][k][l][i],dp[j][k-1][((l<<2)+3)&((1<<12)-1)][i-1]);
						}
					}
				}
			}
		}
	}
	int ret=0;
	for(int i=0;i<=c;i++)
		for(int j=0;j<(1<<12);j++)ret=max(ret,dp[a-1][b-1][j][i]);
	printf("%d\n",ret);
}