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

用位操作，每个状态用两个字节而已

Posted by LacusClyne at 2008-07-13 10:39:32 on Problem 1753

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
	unsigned short initialState = 0;
	bool beUsed[65535];
	char ch;
	unsigned short stateList[70000];
	int timesOfMoving[70000];
	int counter = 0;
	unsigned short maskCode;
	
	memset( stateList, 0, sizeof( stateList ) );
	memset( beUsed, false, sizeof( beUsed ) );
	memset( timesOfMoving, 0, sizeof( timesOfMoving ) );
	int front, tail;
	for ( int i=0; i<16; i++ ) {
		cin>>ch;
		initialState *= 2;
		initialState += (ch=='b')?1:0;
	}
//	cout<<sizeof( initialState )<<endl;

	stateList[0] = initialState; 
	beUsed[ initialState ] = true;
	front = 0;
	tail = 0;
	if ( initialState == 65535 ) {
		cout<<0<<endl;
	}
	else 	while ( 1 ) {
		if ( front > tail ) {
			cout<<"Impossible"<<endl;
			cout<<front<<' '<<tail<<endl;
			cout<<stateList[0]<<endl<<stateList[1]<<endl<<stateList[2]<<endl<<stateList[3]<<endl;
			break;
		}
		maskCode = 0xC800;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0xE400;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x7200;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x3100;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x8C80;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x4E40;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x2720;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x1310;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x08C8;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x04E4;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x0272;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x0131;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x008C;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x004E;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x0027;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		//
		maskCode = 0x0013;
		if ( !beUsed[ stateList[front]^maskCode ] ) {
			beUsed[ stateList[front]^maskCode ] = true;
			stateList[++tail] = stateList[front]^maskCode;
			timesOfMoving[tail] = timesOfMoving[front]+1;
			if ( stateList[tail] == 65535 ) {
				cout<<timesOfMoving[tail]<<endl;
				break;
			}
		}
		
		++front;
		
	}

	
    system("PAUSE");
    return EXIT_SUCCESS;
}

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> #include <cstdlib>
> #include <iostream>
> 
> using namespace std;
> 
> int main(int argc, char *argv[])
> {
> 	unsigned short initialState = 0;
> 	bool beUsed[65535];
> 	char ch;
> 	unsigned short stateList[70000];
> 	int timesOfMoving[70000];
> 	int counter = 0;
> 	unsigned short maskCode;
> 	
> 	memset( stateList, 0, sizeof( stateList ) );
> 	memset( beUsed, false, sizeof( beUsed ) );
> 	memset( timesOfMoving, 0, sizeof( timesOfMoving ) );
> 	int front, tail;
> 	for ( int i=0; i<16; i++ ) {
> 		cin>>ch;
> 		initialState *= 2;
> 		initialState += (ch=='b')?1:0;
> 	}
> //	cout<<sizeof( initialState )<<endl;
> 
> 	stateList[0] = initialState; 
> 	beUsed[ initialState ] = true;
> 	front = 0;
> 	tail = 0;
> 	if ( initialState == 65535 ) {
> 		cout<<0<<endl;
> 	}
> 	else 	while ( 1 ) {
> 		if ( front > tail ) {
> 			cout<<"Impossible"<<endl;
> 			cout<<front<<' '<<tail<<endl;
> 			cout<<stateList[0]<<endl<<stateList[1]<<endl<<stateList[2]<<endl<<stateList[3]<<endl;
> 			break;
> 		}
> 		maskCode = 0xC800;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0xE400;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x7200;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x3100;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x8C80;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x4E40;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x2720;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x1310;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x08C8;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x04E4;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x0272;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x0131;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x008C;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x004E;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x0027;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		//
> 		maskCode = 0x0013;
> 		if ( !beUsed[ stateList[front]^maskCode ] ) {
> 			beUsed[ stateList[front]^maskCode ] = true;
> 			stateList[++tail] = stateList[front]^maskCode;
> 			timesOfMoving[tail] = timesOfMoving[front]+1;
> 			if ( stateList[tail] == 65535 ) {
> 				cout<<timesOfMoving[tail]<<endl;
> 				break;
> 			}
> 		}
> 		
> 		++front;
> 		
> 	}
> 
> 	
>     system("PAUSE");
>     return EXIT_SUCCESS;
> }

Home Page Go Back To top