Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

沙发？写的累死了，dfs+各种剪枝，0ms水过

Posted by KatrineYang at 2016-08-26 12:09:59 on Problem 1213 and last updated at 2016-08-26 12:10:55

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
char data[30];
int romeVal[256];
int jiapos, dengpos;
char *c1, *c2, *c3;
int l1, l2, l3;
int cnt;

bool bnZero[128];

int dfs(int ws, int *val, bool *used, int carry);

void init(){
	romeVal['I'] = 1, romeVal['X'] = 10, romeVal['C'] = 100, romeVal['M'] = 1000;
	romeVal['V'] = 5, romeVal['L'] = 50, romeVal['D'] = 500;
}

int toRome(char *data, int len){
	int sum = 0;
	for(int i = 0; i < len; i++){
		if(i != len-1 && romeVal[(int)data[i]] < romeVal[(int)data[i+1]]){
			sum -= romeVal[(int)data[i]];
		}
		else sum += romeVal[(int)data[i]];
	}
	return sum;
}

int main() {
	init();

	while(1){
		scanf("%s", data);
		if(data[0] == '#') break;

		int len = strlen(data);
		for(int i = 0; i < len; i++){
			if(data[i] == '+'){
				jiapos = i;
			}
			if(data[i] == '='){
				dengpos = i;
				break;
			}
		}
		int rome1 = toRome(data, jiapos), rome2 = toRome(data+jiapos+1, dengpos-jiapos-1), rome3 = toRome(data+dengpos+1, len-dengpos-1);
		//cout << rome1 << " " << rome2 << " " << rome3 << endl;
		if(rome1 + rome2 == rome3){
			printf("Correct ");
		}
		else{
			printf("Incorrect ");
		}
		c1 = data, c2 = data+jiapos+1, c3 = data + dengpos +1;
		l1 = jiapos, l2 = dengpos-jiapos-1, l3 = len-dengpos-1;
		if(l1 < l2){
			int temp = l1;
			l1 = l2;
			l2 = temp;
			char *tmp = c1;
			c1 = c2;
			c2 = tmp;
		}
		if(l3 < l1 || l3 < l2){
			printf("impossible\n");
			continue;
		}
		if(l3 > l1+1 && l3 > l2+1){
			printf("impossible\n");
			continue;
		}
		int val[128];
		bool used[10] = {0};
		for(int i = 'C'; i <= 'X'; i++) val[i] = -1;
		cnt = 0;
		for(int i = 'C'; i <= 'X'; i++) bnZero[i] = 0;
		bnZero[c1[0]] = 1, bnZero[c2[0]] = 1, bnZero[c3[0]] = 1;
		int res = dfs(0, val, used, 0);
		if(res == 0) printf("impossible\n");
		if(res == 1) printf("valid\n");
		if(res == 2) printf("ambiguous\n");
	}
	return 0;
}

int dfs(int ws, int *val, bool *used, int carry){
	if(ws == l3){
		if(carry == 0) cnt ++;
		if(cnt > 1) return 2;
		return cnt;
	}
	if(ws < l2){
		//此时1,2,3都在
		bool cz[4];
		char vr1 = c1[l1-ws-1], vr2 = c2[l2-ws-1], vr3 = c3[l3-ws-1];
		int v1 = val[vr1], v2 = val[vr2], v3 = val[vr3];
		cz[1] = (v1 != -1);
		cz[2] = (v2 != -1);
		cz[3] = (v3 != -1);

		if(cz[1] && cz[2] && cz[3]){

			if((v1+v2+carry)%10==v3){
				if(v1+v2+carry >= 10){
					if(dfs(ws+1, val, used, 1) == 2) return 2;
				}
				else{
					if(dfs(ws+1, val, used, 0) == 2) return 2;
				}
			}
		}

		else if(cz[1] && cz[2] && !cz[3]){
			v3 = (v1+v2+carry)%10;
			bool bx = used[v3] || (v3 == 0 && bnZero[vr3]);
			if(!bx){
				used[v3] = 1;
				val[vr3] = v3;
				int cry = (v1+v2+carry>=10) ? 1 : 0;
				if(dfs(ws+1, val, used, cry) == 2) return 2;
				val[vr3] = -1;
				used[v3] = 0;
			}
		}

		else if(cz[1] && !cz[2] && cz[3]){
			v2 = (v3+20-v1-carry)%10;
			bool bx = used[v2] || (v2 == 0 && bnZero[vr2]);
			if(!bx){
				used[v2] = 1;
				val[vr2] = v2;
				int cry = (v1+v2+carry>=10) ? 1 : 0;
				if(dfs(ws+1, val, used, cry) == 2) return 2;
				val[vr2] = -1;
				used[v2] = 0;
			}
		}

		else if(!cz[1] && cz[2] && cz[3]){
			v1 = (v3+20-v2-carry)%10;
			bool bx = used[v1] || (v1 == 0 && bnZero[vr1]);
			if(!bx){
				used[v1] = 1;
				val[vr1] = v1;
				int cry = (v1+v2+carry>=10) ? 1 : 0;
				if(dfs(ws+1, val, used, cry) == 2) return 2;
				val[vr1] = -1;
				used[v1] = 0;
			}
		}

		else if(cz[1] && !cz[2] && !cz[3]){
			for(v2 = 0; v2 <= 9; v2++){
				if(used[v2] || (v2 == 0 && bnZero[vr2])) continue;
				v3 = (v1+v2+carry)%10;
				bool bx = 0;
				if(used[v3] || (v3 == 0 && bnZero[vr3])) bx = 1;
				else if(v2 == v3 && vr2 != vr3) bx = 1;
				else if(v2 != v3 && vr2 == vr3) bx = 1;
				if(bx) continue;
				used[v2] = 1;
				used[v3] = 1;
				val[vr2] = v2;
				val[vr3] = v3;
				int cry = (v1+v2+carry>=10) ? 1 : 0;
				if(dfs(ws+1, val, used, cry) == 2) return 2;
				used[v2] = 0;
				used[v3] = 0;
				val[vr2] = -1;
				val[vr3] = -1;
			}
		}

		else if(!cz[1] && cz[2] && !cz[3]){
			for(v1 = 0; v1 <= 9; v1++){
				if(used[v1] || (v1 == 0 && bnZero[vr1])) continue;
				v3 = (v1+v2+carry)%10;
				bool bx = 0;
				if(used[v3] || (v3 == 0 && bnZero[vr3])) bx = 1;
				else if(v1 == v3 && vr1 != vr3) bx = 1;
				else if(v1 != v3 && vr1 == vr3) bx = 1;
				if(bx) continue;
				used[v1] = 1;
				used[v3] = 1;
				val[vr1] = v1;
				val[vr3] = v3;
				int cry = (v1+v2+carry>=10) ? 1 : 0;
				if(dfs(ws+1, val, used, cry) == 2) return 2;
				used[v1] = 0;
				used[v3] = 0;
				val[vr1] = -1;
				val[vr3] = -1;
			}
		}

		else if(!cz[1] && !cz[2] && cz[3]){
			for(v2 = 0; v2 <= 9; v2++){
				if(used[v2] || (v2 == 0 && bnZero[vr2])) continue;
				v1 = (v3+20-v2-carry)%10;
				bool bx = 0;
				if(used[v1] || (v1 == 0 && bnZero[vr1])) bx = 1;
				else if(v2 == v1 && vr2 != vr1) bx = 1;
				else if(v2 != v1 && vr2 == vr1) bx = 1;
				if(bx) continue;
				used[v2] = 1;
				used[v1] = 1;
				val[vr2] = v2;
				val[vr1] = v1;
				int cry = (v1+v2+carry>=10) ? 1 : 0;
				if(dfs(ws+1, val, used, cry) == 2) return 2;
				used[v2] = 0;
				used[v1] = 0;
				val[vr2] = -1;
				val[vr1] = -1;
			}
		}

		else{
			for(v1 = 0; v1 <= 9; v1++){
				if(used[v1] || (v1 == 0 && bnZero[vr1])) continue;
				for(v2 = 0; v2 <= 9; v2++){
					if(used[v2] || (v2 == 0 && bnZero[vr2])) continue;

					v3 = (v1+v2+carry)%10;

					if(!used[v3] && (v3 != 0 || !bnZero[vr3])){

						bool bx = 0;
						if(v1 == v2 && vr1 != vr2) bx = 1;
						else if(v1 != v2 && vr1 == vr2) bx = 1;
						else if(v1 == v3 && vr1 != vr3) bx = 1;
						else if(v1 != v3 && vr1 == vr3) bx = 1;
						else if(v2 == v3 && vr2 != vr3) bx = 1;
						else if(v2 != v3 && vr2 == vr3) bx = 1;
						if(bx) continue;
						used[v1] = 1;
						used[v2] = 1;
						used[v3] = 1;
						val[vr1] = v1;
						val[vr2] = v2;
						val[vr3] = v3;
						int cry = (v1+v2+carry>=10) ? 1 : 0;
						if(dfs(ws+1, val, used, cry) == 2) return 2;
						used[v1] = 0;
						used[v2] = 0;
						used[v3] = 0;
						val[vr1] = -1;
						val[vr2] = -1;
						val[vr3] = -1;
					}


				}

			}
		}

	}
	else if(ws < l1){
		//只有1和3
		bool cz[4];
		char vr1 = c1[l1-ws-1], vr3 = c3[l3-ws-1];
		int v1 = val[vr1], v3 = val[vr3];
		cz[1] = (v1 != -1);
		cz[3] = (v3 != -1);

		if(cz[1] && cz[3]){
			if((v1+carry)%10 == v3){
				int cry = (v1+carry >= 10) ? 1 : 0;
				if(dfs(ws+1, val, used, cry) == 2) return 2;
			}
		}

		else if(cz[1] && !cz[3]){
			v3 = (v1+carry)%10;
			bool bx = used[v3] || (v3 == 0 && bnZero[vr3]);
			if(!bx){
				used[v3] = 1;
				val[vr3] = v3;
				int cry = (v1+carry >= 10) ? 1 : 0;
				if(dfs(ws+1, val, used, cry) == 2) return 2;
				used[v3] = 0;
				val[vr3] = -1;
			}
		}

		else if(!cz[1] && cz[3]){
			v1 = (v3+10-carry)%10;
			bool bx = used[v1] || (v1 == 0 && bnZero[vr1]);
			if(!bx){
				used[v1] = 1;
				val[vr1] = v1;
				int cry = (v1+carry >= 10) ? 1 : 0;
				if(dfs(ws+1, val, used, cry) == 2) return 2;
				used[v1] = 0;
				val[vr1] = -1;
			}
		}

		else{
			for(v1 = 0; v1 <= 9; v1++){
				if(used[v1] || (v1 == 0 && bnZero[vr1])) continue;
				v3 = (v1+carry)%10;
				bool bx = 0;
				if(used[v3] || (v3 == 0 && bnZero[vr3])) bx = 1;
				else if(v1 == v3 && vr1 != vr3) bx = 1;
				else if(v1 != v3 && vr1 == vr3) bx = 1;
				if(bx) continue;
				used[v1] = 1;
				val[vr1] = v1;
				used[v3] = 1;
				val[vr3] = v3;
				int cry = (v1+carry >= 10) ? 1 : 0;
				if(dfs(ws+1, val, used, cry) == 2) return 2;
				used[v1] = 0;
				val[vr1] = -1;
				used[v3] = 0;
				val[vr3] = -1;
			}
		}

	}
	else{
		//只有3
		char vr3 = c3[l3-ws-1];
		int v3 = val[vr3];
		if(v3 == 1 && carry == 1){
			if(dfs(ws+1, val, used, 0) == 2) return 2;
		}
		if(v3 == -1 && !used[1] && carry == 1){
			v3 = 1;
			used[1] = 1;
			val[vr3] = 1;
			if(dfs(ws+1, val, used, 0) == 2) return 2;
			used[1] = 0;
			val[vr3] = -1;
		}
	}
	return cnt;
}

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> #include <iostream>
> #include <stdio.h>
> #include <string.h>
> using namespace std;
> char data[30];
> int romeVal[256];
> int jiapos, dengpos;
> char *c1, *c2, *c3;
> int l1, l2, l3;
> int cnt;
> 
> bool bnZero[128];
> 
> int dfs(int ws, int *val, bool *used, int carry);
> 
> void init(){
> 	romeVal['I'] = 1, romeVal['X'] = 10, romeVal['C'] = 100, romeVal['M'] = 1000;
> 	romeVal['V'] = 5, romeVal['L'] = 50, romeVal['D'] = 500;
> }
> 
> int toRome(char *data, int len){
> 	int sum = 0;
> 	for(int i = 0; i < len; i++){
> 		if(i != len-1 && romeVal[(int)data[i]] < romeVal[(int)data[i+1]]){
> 			sum -= romeVal[(int)data[i]];
> 		}
> 		else sum += romeVal[(int)data[i]];
> 	}
> 	return sum;
> }
> 
> int main() {
> 	init();
> 
> 	while(1){
> 		scanf("%s", data);
> 		if(data[0] == '#') break;
> 
> 		int len = strlen(data);
> 		for(int i = 0; i < len; i++){
> 			if(data[i] == '+'){
> 				jiapos = i;
> 			}
> 			if(data[i] == '='){
> 				dengpos = i;
> 				break;
> 			}
> 		}
> 		int rome1 = toRome(data, jiapos), rome2 = toRome(data+jiapos+1, dengpos-jiapos-1), rome3 = toRome(data+dengpos+1, len-dengpos-1);
> 		//cout << rome1 << " " << rome2 << " " << rome3 << endl;
> 		if(rome1 + rome2 == rome3){
> 			printf("Correct ");
> 		}
> 		else{
> 			printf("Incorrect ");
> 		}
> 		c1 = data, c2 = data+jiapos+1, c3 = data + dengpos +1;
> 		l1 = jiapos, l2 = dengpos-jiapos-1, l3 = len-dengpos-1;
> 		if(l1 < l2){
> 			int temp = l1;
> 			l1 = l2;
> 			l2 = temp;
> 			char *tmp = c1;
> 			c1 = c2;
> 			c2 = tmp;
> 		}
> 		if(l3 < l1 || l3 < l2){
> 			printf("impossible\n");
> 			continue;
> 		}
> 		if(l3 > l1+1 && l3 > l2+1){
> 			printf("impossible\n");
> 			continue;
> 		}
> 		int val[128];
> 		bool used[10] = {0};
> 		for(int i = 'C'; i <= 'X'; i++) val[i] = -1;
> 		cnt = 0;
> 		for(int i = 'C'; i <= 'X'; i++) bnZero[i] = 0;
> 		bnZero[c1[0]] = 1, bnZero[c2[0]] = 1, bnZero[c3[0]] = 1;
> 		int res = dfs(0, val, used, 0);
> 		if(res == 0) printf("impossible\n");
> 		if(res == 1) printf("valid\n");
> 		if(res == 2) printf("ambiguous\n");
> 	}
> 	return 0;
> }
> 
> int dfs(int ws, int *val, bool *used, int carry){
> 	if(ws == l3){
> 		if(carry == 0) cnt ++;
> 		if(cnt > 1) return 2;
> 		return cnt;
> 	}
> 	if(ws < l2){
> 		//此时1,2,3都在
> 		bool cz[4];
> 		char vr1 = c1[l1-ws-1], vr2 = c2[l2-ws-1], vr3 = c3[l3-ws-1];
> 		int v1 = val[vr1], v2 = val[vr2], v3 = val[vr3];
> 		cz[1] = (v1 != -1);
> 		cz[2] = (v2 != -1);
> 		cz[3] = (v3 != -1);
> 
> 		if(cz[1] && cz[2] && cz[3]){
> 
> 			if((v1+v2+carry)%10==v3){
> 				if(v1+v2+carry >= 10){
> 					if(dfs(ws+1, val, used, 1) == 2) return 2;
> 				}
> 				else{
> 					if(dfs(ws+1, val, used, 0) == 2) return 2;
> 				}
> 			}
> 		}
> 
> 		else if(cz[1] && cz[2] && !cz[3]){
> 			v3 = (v1+v2+carry)%10;
> 			bool bx = used[v3] || (v3 == 0 && bnZero[vr3]);
> 			if(!bx){
> 				used[v3] = 1;
> 				val[vr3] = v3;
> 				int cry = (v1+v2+carry>=10) ? 1 : 0;
> 				if(dfs(ws+1, val, used, cry) == 2) return 2;
> 				val[vr3] = -1;
> 				used[v3] = 0;
> 			}
> 		}
> 
> 		else if(cz[1] && !cz[2] && cz[3]){
> 			v2 = (v3+20-v1-carry)%10;
> 			bool bx = used[v2] || (v2 == 0 && bnZero[vr2]);
> 			if(!bx){
> 				used[v2] = 1;
> 				val[vr2] = v2;
> 				int cry = (v1+v2+carry>=10) ? 1 : 0;
> 				if(dfs(ws+1, val, used, cry) == 2) return 2;
> 				val[vr2] = -1;
> 				used[v2] = 0;
> 			}
> 		}
> 
> 		else if(!cz[1] && cz[2] && cz[3]){
> 			v1 = (v3+20-v2-carry)%10;
> 			bool bx = used[v1] || (v1 == 0 && bnZero[vr1]);
> 			if(!bx){
> 				used[v1] = 1;
> 				val[vr1] = v1;
> 				int cry = (v1+v2+carry>=10) ? 1 : 0;
> 				if(dfs(ws+1, val, used, cry) == 2) return 2;
> 				val[vr1] = -1;
> 				used[v1] = 0;
> 			}
> 		}
> 
> 		else if(cz[1] && !cz[2] && !cz[3]){
> 			for(v2 = 0; v2 <= 9; v2++){
> 				if(used[v2] || (v2 == 0 && bnZero[vr2])) continue;
> 				v3 = (v1+v2+carry)%10;
> 				bool bx = 0;
> 				if(used[v3] || (v3 == 0 && bnZero[vr3])) bx = 1;
> 				else if(v2 == v3 && vr2 != vr3) bx = 1;
> 				else if(v2 != v3 && vr2 == vr3) bx = 1;
> 				if(bx) continue;
> 				used[v2] = 1;
> 				used[v3] = 1;
> 				val[vr2] = v2;
> 				val[vr3] = v3;
> 				int cry = (v1+v2+carry>=10) ? 1 : 0;
> 				if(dfs(ws+1, val, used, cry) == 2) return 2;
> 				used[v2] = 0;
> 				used[v3] = 0;
> 				val[vr2] = -1;
> 				val[vr3] = -1;
> 			}
> 		}
> 
> 		else if(!cz[1] && cz[2] && !cz[3]){
> 			for(v1 = 0; v1 <= 9; v1++){
> 				if(used[v1] || (v1 == 0 && bnZero[vr1])) continue;
> 				v3 = (v1+v2+carry)%10;
> 				bool bx = 0;
> 				if(used[v3] || (v3 == 0 && bnZero[vr3])) bx = 1;
> 				else if(v1 == v3 && vr1 != vr3) bx = 1;
> 				else if(v1 != v3 && vr1 == vr3) bx = 1;
> 				if(bx) continue;
> 				used[v1] = 1;
> 				used[v3] = 1;
> 				val[vr1] = v1;
> 				val[vr3] = v3;
> 				int cry = (v1+v2+carry>=10) ? 1 : 0;
> 				if(dfs(ws+1, val, used, cry) == 2) return 2;
> 				used[v1] = 0;
> 				used[v3] = 0;
> 				val[vr1] = -1;
> 				val[vr3] = -1;
> 			}
> 		}
> 
> 		else if(!cz[1] && !cz[2] && cz[3]){
> 			for(v2 = 0; v2 <= 9; v2++){
> 				if(used[v2] || (v2 == 0 && bnZero[vr2])) continue;
> 				v1 = (v3+20-v2-carry)%10;
> 				bool bx = 0;
> 				if(used[v1] || (v1 == 0 && bnZero[vr1])) bx = 1;
> 				else if(v2 == v1 && vr2 != vr1) bx = 1;
> 				else if(v2 != v1 && vr2 == vr1) bx = 1;
> 				if(bx) continue;
> 				used[v2] = 1;
> 				used[v1] = 1;
> 				val[vr2] = v2;
> 				val[vr1] = v1;
> 				int cry = (v1+v2+carry>=10) ? 1 : 0;
> 				if(dfs(ws+1, val, used, cry) == 2) return 2;
> 				used[v2] = 0;
> 				used[v1] = 0;
> 				val[vr2] = -1;
> 				val[vr1] = -1;
> 			}
> 		}
> 
> 		else{
> 			for(v1 = 0; v1 <= 9; v1++){
> 				if(used[v1] || (v1 == 0 && bnZero[vr1])) continue;
> 				for(v2 = 0; v2 <= 9; v2++){
> 					if(used[v2] || (v2 == 0 && bnZero[vr2])) continue;
> 
> 					v3 = (v1+v2+carry)%10;
> 
> 					if(!used[v3] && (v3 != 0 || !bnZero[vr3])){
> 
> 						bool bx = 0;
> 						if(v1 == v2 && vr1 != vr2) bx = 1;
> 						else if(v1 != v2 && vr1 == vr2) bx = 1;
> 						else if(v1 == v3 && vr1 != vr3) bx = 1;
> 						else if(v1 != v3 && vr1 == vr3) bx = 1;
> 						else if(v2 == v3 && vr2 != vr3) bx = 1;
> 						else if(v2 != v3 && vr2 == vr3) bx = 1;
> 						if(bx) continue;
> 						used[v1] = 1;
> 						used[v2] = 1;
> 						used[v3] = 1;
> 						val[vr1] = v1;
> 						val[vr2] = v2;
> 						val[vr3] = v3;
> 						int cry = (v1+v2+carry>=10) ? 1 : 0;
> 						if(dfs(ws+1, val, used, cry) == 2) return 2;
> 						used[v1] = 0;
> 						used[v2] = 0;
> 						used[v3] = 0;
> 						val[vr1] = -1;
> 						val[vr2] = -1;
> 						val[vr3] = -1;
> 					}
> 
> 
> 				}
> 
> 			}
> 		}
> 
> 	}
> 	else if(ws < l1){
> 		//只有1和3
> 		bool cz[4];
> 		char vr1 = c1[l1-ws-1], vr3 = c3[l3-ws-1];
> 		int v1 = val[vr1], v3 = val[vr3];
> 		cz[1] = (v1 != -1);
> 		cz[3] = (v3 != -1);
> 
> 		if(cz[1] && cz[3]){
> 			if((v1+carry)%10 == v3){
> 				int cry = (v1+carry >= 10) ? 1 : 0;
> 				if(dfs(ws+1, val, used, cry) == 2) return 2;
> 			}
> 		}
> 
> 		else if(cz[1] && !cz[3]){
> 			v3 = (v1+carry)%10;
> 			bool bx = used[v3] || (v3 == 0 && bnZero[vr3]);
> 			if(!bx){
> 				used[v3] = 1;
> 				val[vr3] = v3;
> 				int cry = (v1+carry >= 10) ? 1 : 0;
> 				if(dfs(ws+1, val, used, cry) == 2) return 2;
> 				used[v3] = 0;
> 				val[vr3] = -1;
> 			}
> 		}
> 
> 		else if(!cz[1] && cz[3]){
> 			v1 = (v3+10-carry)%10;
> 			bool bx = used[v1] || (v1 == 0 && bnZero[vr1]);
> 			if(!bx){
> 				used[v1] = 1;
> 				val[vr1] = v1;
> 				int cry = (v1+carry >= 10) ? 1 : 0;
> 				if(dfs(ws+1, val, used, cry) == 2) return 2;
> 				used[v1] = 0;
> 				val[vr1] = -1;
> 			}
> 		}
> 
> 		else{
> 			for(v1 = 0; v1 <= 9; v1++){
> 				if(used[v1] || (v1 == 0 && bnZero[vr1])) continue;
> 				v3 = (v1+carry)%10;
> 				bool bx = 0;
> 				if(used[v3] || (v3 == 0 && bnZero[vr3])) bx = 1;
> 				else if(v1 == v3 && vr1 != vr3) bx = 1;
> 				else if(v1 != v3 && vr1 == vr3) bx = 1;
> 				if(bx) continue;
> 				used[v1] = 1;
> 				val[vr1] = v1;
> 				used[v3] = 1;
> 				val[vr3] = v3;
> 				int cry = (v1+carry >= 10) ? 1 : 0;
> 				if(dfs(ws+1, val, used, cry) == 2) return 2;
> 				used[v1] = 0;
> 				val[vr1] = -1;
> 				used[v3] = 0;
> 				val[vr3] = -1;
> 			}
> 		}
> 
> 	}
> 	else{
> 		//只有3
> 		char vr3 = c3[l3-ws-1];
> 		int v3 = val[vr3];
> 		if(v3 == 1 && carry == 1){
> 			if(dfs(ws+1, val, used, 0) == 2) return 2;
> 		}
> 		if(v3 == -1 && !used[1] && carry == 1){
> 			v3 = 1;
> 			used[1] = 1;
> 			val[vr3] = 1;
> 			if(dfs(ws+1, val, used, 0) == 2) return 2;
> 			used[1] = 0;
> 			val[vr3] = -1;
> 		}
> 	}
> 	return cnt;
> }
>

Home Page Go Back To top