Boggle
Problem's Link: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1457
Mean:
给定n个串，有m个询问。
每个询问给你一个4*4的字符矩阵，你可以在这个字符矩阵中任意字符出发，向四个方向走（已走过的不可重复走），走出一个字符串。
如果n个串中有对应的串和走出的字符串相同，那么需要求出：
1.不同长度的串给了不同的权值，n个串中出现的串的总权值是多少？
2.从出现的字符串中找一个最长的出来，如果有多个，找一个字典序最小的。
3.n个串中总共出现了多少个串？
analyse:
Trie树+DFS.
一开始我是将矩阵的dfs串加入到Trie树中，然后用n个串来匹配树，各种TLE。
后来算了一下时间复杂度，很明显将n个串插入到Trie树中，再用矩阵的dfs串去匹配树，这样更优。
当然这样的话就要自己写字典序的比较函数，也很简单，其他地方没什么坑，写的时候细心一点就行。
Time complexity: O(N+M)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-27-13.27
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);
int score , num;
bool v [ 5000010 ], vv [ 10 ][ 10 ];
int dx [] = { 1 , 1 , 0 , - 1 , - 1 , - 1 , 0 , 1 };
int dy [] = { 0 , 1 , 1 , 1 , 0 , - 1 , - 1 , - 1 };
int val [] = { 0 , 0 , 0 , 1 , 1 , 2 , 3 , 5 , 11 , 11 , 11 };
char str [ 300010 ][ 10 ], Mat [ 4 ][ 5 ], ans [ 10 ], tmp [ 10 ];
struct node
{
node * Next [ 26 ];
int sc , num;
bool flag;
node()
{
for( int i = 0; i < 26; ++ i) Next [ i ] = NULL;
num = 0 , sc =- 1;
}
} * root;
void Insert( char *s , int id)
{
node *p = root;
int i = 0 , idx;
while(s [ i ])
{
idx =s [ i ] - 'A';
if(p -> Next [ idx ] == NULL)
p -> Next [ idx ] = new node();
p =p -> Next [ idx ];
++ i;
}
p -> num = id;
p -> sc = val [ strlen(s )];
}
void Matching( char *s)
{
int i = 0 , idx;
node *p = root;
int len = strlen(s);
while(s [ i ])
{
idx =s [ i ] - 'A';
if(p -> Next [ idx ] == NULL) break;
p =p -> Next [ idx ];
++ i;
}
if( v [p -> num ] == false && p -> sc !=- 1)
{
++ num;
score +=p -> sc;
v [p -> num ] = true;
if( num == 1 || ( strlen(s) > strlen( ans)) || (( strlen(s) == strlen( ans) && strcmp(s , ans) < 0)) )
memcpy( ans ,s , 10);
}
}
void dfs( int x , int y , int cnt)
{
if( cnt > 8) return;
tmp [ cnt - 1 ] = Mat [ x ][ y ];
tmp [ cnt ] = '\0';
Matching( tmp);
vv [ x ][ y ] = true;
for( int i = 0; i < 8; ++ i)
{
int xx = x + dx [ i ];
int yy = y + dy [ i ];
if( vv [ xx ][ yy ] != true && ( xx >= 0 && xx < 4 && yy >= 0 && yy < 4))
{
vv [ x ][ y ] = 1;
dfs( xx , yy , cnt + 1);
vv [ x ][ y ] = 0;
}
}
vv [ x ][ y ] = 0;
}
int main()
{
ios_base :: sync_with_stdio( false);
cin . tie( 0);
int n , m;
scanf( "%d" , &n);
root = new node();
for( int i = 0; i <n; ++ i)
{
scanf( "%s" , str [ i ]);
Insert( str [ i ], i);
}
scanf( "%d" , & m);
while( m --)
{
memset( v , 0 , sizeof v);
score = num = 0;
for( int i = 0; i < 4; ++ i)
scanf( "%s" , Mat [ i ]);
for( int i = 0; i < 4; ++ i)
for( int j = 0; j < 4; ++ j)
dfs( i , j , 1);
printf( "%d %s %d \n " , score , ans , num);
}
return 0;
}
/*
*/
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-27-13.27
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);
int score , num;
bool v [ 5000010 ], vv [ 10 ][ 10 ];
int dx [] = { 1 , 1 , 0 , - 1 , - 1 , - 1 , 0 , 1 };
int dy [] = { 0 , 1 , 1 , 1 , 0 , - 1 , - 1 , - 1 };
int val [] = { 0 , 0 , 0 , 1 , 1 , 2 , 3 , 5 , 11 , 11 , 11 };
char str [ 300010 ][ 10 ], Mat [ 4 ][ 5 ], ans [ 10 ], tmp [ 10 ];
struct node
{
node * Next [ 26 ];
int sc , num;
bool flag;
node()
{
for( int i = 0; i < 26; ++ i) Next [ i ] = NULL;
num = 0 , sc =- 1;
}
} * root;
void Insert( char *s , int id)
{
node *p = root;
int i = 0 , idx;
while(s [ i ])
{
idx =s [ i ] - 'A';
if(p -> Next [ idx ] == NULL)
p -> Next [ idx ] = new node();
p =p -> Next [ idx ];
++ i;
}
p -> num = id;
p -> sc = val [ strlen(s )];
}
void Matching( char *s)
{
int i = 0 , idx;
node *p = root;
int len = strlen(s);
while(s [ i ])
{
idx =s [ i ] - 'A';
if(p -> Next [ idx ] == NULL) break;
p =p -> Next [ idx ];
++ i;
}
if( v [p -> num ] == false && p -> sc !=- 1)
{
++ num;
score +=p -> sc;
v [p -> num ] = true;
if( num == 1 || ( strlen(s) > strlen( ans)) || (( strlen(s) == strlen( ans) && strcmp(s , ans) < 0)) )
memcpy( ans ,s , 10);
}
}
void dfs( int x , int y , int cnt)
{
if( cnt > 8) return;
tmp [ cnt - 1 ] = Mat [ x ][ y ];
tmp [ cnt ] = '\0';
Matching( tmp);
vv [ x ][ y ] = true;
for( int i = 0; i < 8; ++ i)
{
int xx = x + dx [ i ];
int yy = y + dy [ i ];
if( vv [ xx ][ yy ] != true && ( xx >= 0 && xx < 4 && yy >= 0 && yy < 4))
{
vv [ x ][ y ] = 1;
dfs( xx , yy , cnt + 1);
vv [ x ][ y ] = 0;
}
}
vv [ x ][ y ] = 0;
}
int main()
{
ios_base :: sync_with_stdio( false);
cin . tie( 0);
int n , m;
scanf( "%d" , &n);
root = new node();
for( int i = 0; i <n; ++ i)
{
scanf( "%s" , str [ i ]);
Insert( str [ i ], i);
}
scanf( "%d" , & m);
while( m --)
{
memset( v , 0 , sizeof v);
score = num = 0;
for( int i = 0; i < 4; ++ i)
scanf( "%s" , Mat [ i ]);
for( int i = 0; i < 4; ++ i)
for( int j = 0; j < 4; ++ j)
dfs( i , j , 1);
printf( "%d %s %d \n " , score , ans , num);
}
return 0;
}
/*
*/
