紫书习题7-8 UVa 12107 (IDA*)

参考了这哥们的博客 https://blog.csdn.net/hyqsblog/article/details/46980287

(1)atoi可以char数组转int, 头文件 cstdlib

(2)小技巧，倒过来存是用[len-i-1]

(3)这道题的关键在于怎么去构造这个搜索，以什么方式去搜索。这里搜索专门用两个参数来控制第几个数的第几个位置，还有一个参数是改变的次数，也就是深度。这里还要逆向思维，check的时候最后一个数， 可以不用递归了，而是由前面两个数反过来推然后判断符不符合，可以省去很多时间

#include<cstdio>

#include<cstdlib>

#include<cstring>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 10;

const char* word = "*0123456789";

char s[MAXN][MAXN];

int len[MAXN], maxd;

int result()

{

	int num = atoi(s[0]) * atoi(s[1]);

	char str[MAXN];

	REP(i, 0, len[2])

	{

		str[len[2]-i-1] = num % 10 + '0';

		num /= 10;

	}

	if(num != 0 || str[0] == '0') return 0;

	REP(i, 0, len[2])

		if(s[2][i] != '*' && str[i] != s[2][i])

			return 0;

	return 1;

}

int check(int id, int pos)

{

	if(id == 2) return result();

	int ta, tb, cnt = 0;

	if(pos == len[id] - 1) { ta = id + 1; tb = 0; }

	else { ta = id; tb = pos + 1; }

	char t = s[id][pos];

	if(s[id][pos] == '*')

		REP(i, 1, 11)

		{

			if(word[i] == '0' && pos == 0) continue;

			s[id][pos] = word[i];

			cnt += check(ta, tb);

			if(cnt > 1) break;

		}

	else cnt += check(ta, tb);

	s[id][pos] = t;

	return cnt;

}

bool dfs(int id, int pos, int d)

{

	if(d == maxd) return check(0, 0) == 1;

	if(id == 3) return false;

	int ta, tb;

	if(pos == len[id] - 1) { ta = id + 1; tb = 0; }

	else { ta = id; tb = pos + 1; }

	char t = s[id][pos];

	REP(i, 0, 11)

	{

		if(word[i] == '0' && pos == 0) continue;

		if(t == word[i])

		{

			if(dfs(ta, tb, d))

				return true;

		}

		else

		{

			s[id][pos] = word[i];

			if(dfs(ta, tb, d + 1)) return true;

			s[id][pos] = t;

		}

	}

	return false;

}

int main()

{

	int kase = 0;

	while(memset(s, 0, sizeof(s)), scanf("%s%s%s", s[0], s[1], s[2]) == 3)

	{

		REP(i, 0, 3) len[i] = strlen(s[i]);

		for(maxd = 0; ; maxd++)

			if(dfs(0, 0, 0))

			{

				printf("Case %d: %s %s %s\n", ++kase, s[0], s[1], s[2]);

				break;

			}

	}

	return 0;

}

巴特西

紫书习题7-8 UVa 12107 (IDA*)

最新文章

热门文章

巴特西

紫书 习题7-8 UVa 12107 (IDA*)

最新文章

热门文章

紫书习题7-8 UVa 12107 (IDA*)