3239801_tle.cpp

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

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

using namespace std;

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

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

string getRoman(int num)
{
	int i;
	string str;

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

bool FIND;
int len;
string num;

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

struct Node
{
	int visited[16][16];
	int i, j;
	int need, now;
};

queue <Node> que;

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

void go(int i,int j)
{
	Node t, s;
	int k;
	int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0}};

	t.i = i;t.j = j;
	memset(t.visited,0,sizeof(t.visited));
	t.need = len-1;
	t.now = 0;
	t.visited[i][j] = 1;
	que.push(t);
	while (!FIND&&!que.empty())
	{
		t = que.front();
		que.pop();
		if (t.need==0)
		{
			FIND = (t.j==m-1);
			continue;
		}
		for (k = 0; k < 4; k++)
		{
			s = t;
			i = s.i+mov[k][0];
			j = s.j+mov[k][1];
			if(valid(i,j)&&!s.visited[i][j]&&num.at(s.now+1)==cor[i][j])
			{
				s.visited[i][j] = 1;
				s.now++;
				s.need--;
				s.i = i;s.j = j;
				que.push(s);
			}
		}
	}
}

void solve()
{
	int i;

	for (i = 0; !FIND && i < n; i++)
	{
		if (cor[i][0]==num.at(0))
		{
			go(i,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++)
	{
		num = getRoman(i);
		len = num.length();
		if(len < m||len > m*n)
			continue;
		solve();
	}
	if(!FIND)
		puts("NO");
	else
		puts(num.c_str());
	return 0;
}