3240081_ac_94ms_184k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

int n, m;
char cor[16][16];

struct node
{
	char str[16];
	int value;
}ronum[13];

bool FIND;
int len;
char num[16];

void getRoman(int nn)
{
	int i;

	strcpy(num,"");
	while (nn!=0)
	{
		for (i = 0; ; i++)
		{
			if(nn >= ronum[i].value)
			{
				strcat(num,ronum[i].str);
				nn -= ronum[i].value;
				break;
			}
		}
	}
}



void init()
{
	ronum[0].value = 1000;strcpy(ronum[0].str,"M");
	ronum[1].value = 900;strcpy(ronum[1].str,"CM");
	ronum[2].value = 500;strcpy(ronum[2].str,"D");
	ronum[3].value = 400;strcpy(ronum[3].str,"CD");
	ronum[4].value = 100;strcpy(ronum[4].str,"C");
	ronum[5].value = 90;strcpy(ronum[5].str,"XC");
	ronum[6].value = 50;strcpy(ronum[6].str,"L");
	ronum[7].value = 40;strcpy(ronum[7].str,"XL");
	ronum[8].value = 10;strcpy(ronum[8].str,"X");
	ronum[9].value = 9;strcpy(ronum[9].str,"IX");
	ronum[10].value = 5;strcpy(ronum[10].str,"V");
	ronum[11].value = 4;strcpy(ronum[11].str,"IV");
	ronum[12].value = 1;strcpy(ronum[12].str,"I");
}

int visited[16][16];

int valid(int i,int j)
{
	return i>=0&&j>=0&&i<n&&j<m;
}

bool fail[16][16][16];
int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0}};

void go(int ii,int jj,int l)
{
	int k;
	int i, j;

	if(l==1)
	{
		FIND = (jj==m-1);
		return ;
	}
	for(k = 0; !FIND&&k < 4; k++)
	{
		i = ii+mov[k][0];
		j = jj+mov[k][1];
		if(valid(i,j)&&!visited[i][j]&&num[len-l+1]==cor[i][j]&&!fail[i][j][l-1])
		{
			visited[i][j] = 1;
			go(i,j,l-1);
			visited[i][j] = 0;
			fail[i][j][l-1] = !FIND;
		}
	}
}

void solve()
{
	int i;

	memset(visited,0,sizeof(visited));
	for (i = 0; !FIND && i < n; i++)
	{
		if (cor[i][0]==num[0])
		{
			visited[i][0] = 1;
			go(i,0,len);
			visited[i][0] = 0;
		}
	}
}

int main()
{
	int i;

	scanf("%d%d",&n,&m);
	for (i = 0; i < n; i++)
	{
		scanf("%s",cor[i]);
	}
	init();
	FIND = false;
	for (i = 1; !FIND && i < 4000; i++)
	{
		getRoman(i);
		len = strlen(num);
		if(len < m||len > m*n)
			continue;
		memset(fail,false,sizeof(fail));
		solve();
	}
	if(!FIND)
		puts("NO");
	else
		puts(num);
	return 0;
}