8号做的hdu上面的题目重现。
A题：Wow! Such Doge!
题意：给你一篇文章，找出其中doge出现的次数，不区分大小写。
思路：字符串大写转小写的函数忘了……一个一个转的。然后find下，每次从find的位置开始找，统计个数就完了。交的时候调试忘记删除了，wa了一次。大水！
C题：Wow! Such City!
题意：用给定的数，通过公式可以求出任意两个城市间的距离。一个人在城市0，求出他到所有城市的最小距离。再用这个距离模M，模完的结果一样的放成一类，求MOD完最小的那类。
思路：一开始以为要快速幂什么的求呢，后来发现不用就一个一个求就好。求完所有的点，刷一下最短路（哎~我图论不好看见就蒙圈，最短路写了好久……渣渣啊~~）。再模下，找出最小的就完了。感觉也很水。
D题：Wow! Such String!
题意：很好懂。给一个N，求一个长度是N的字符串。所求字符串的所有长度大于4的子串不重复。有输出，没有Impossible。
思路：当时的思路是求出所有长度是4的不重复的串。然后把所有的串连成一个字符串（前串的后三个字符和后串的前三个字符相同）。处理的时候出了点小问题。我从aaaa开始拼接字符串，aaaab aaac aaad aaae ……aaayaaazaaa ，前面所有的aaa开头的串都用过了，无法把所有的字符串拼接到一起。然后我想换一个试试，当时好像换的zaaa开始的，长度变长了些但还是没有全部拼合。接下来不知道怎么做了，我又用zzzz开始试了下，奇迹的发现全部拼接完了（现在也不到为什么？），然后这个题就出了。
J题：Tunnels
题意：图上有好多通道（tunnels这个词不认识，英语是硬伤啊！），有个人要走遍所有的通道，每个通道只能通过一次。求最短时间？
思路：题目给出一共只有15个通道，当时想一共才2^15个状态，先BFS预处理求出任意两点之间的距离，再用next_permutation把所有的情况的时间都求一下找个最小的就搞定了。然后就各种RE，找到RE的地方是一个n*n
+ n超了。我开的数组是1000的，n才15不能超啊，不到原因啊，我恨死RE了。后来加个判定就是各种wa，实在调不出来了。完了看看大神的代码，发现思路基本一致，就是后面大神们用的状态压缩DP求得，我用的next_permutation。又写了写发现next_permutation超时了，不到这个坑爹的东西时间复杂度是多少。BFS的求点到点的距离也有些问题，各种小错误。哎，怀念芳姐啊~~有芳姐的话这题就不用我了啊……据说这就是旅行商问题，渣渣又学了一招。
贴上这个巨肯爹的代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define PB push_back
#define clr(a,vel) memset(a,vel,sizeof(a))
#define INF 0x7fffffff
const int MAXN = 17;
const int xa[] = {-1, 1, 0, 0};
const int ya[] = {0, 0, -1, 1};
int n, m;
char g[MAXN+4][MAXN+4];
bool id[MAXN+2][MAXN+2];
bool use[MAXN+2],vis[MAXN+2][MAXN+2];
int dp[1<<MAXN][MAXN];
int dis[MAXN][MAXN];
int sun[MAXN];
struct point{
int xs, ys, xe, ye;
}p[MAXN];
struct shortdis{
int x, y, dis;
};
inline void bfs(int pos){
clr(use, 0), clr(vis, 0);
shortdis vn, vm;
vn.x = p[pos].xe, vn.y = p[pos].ye, vn.dis = 0;
queue <shortdis> q;
q.push(vn);
int num = 0;
while(!q.empty()){
vn = q.front();
q.pop();
if(id[vn.x][vn.y]){
for(int i = 0; i < m; i ++){
if(vn.x == p[i].xs && vn.y == p[i].ys && !use[i] && i != pos){
dis[pos][i] = vn.dis;
use[i] = 1;
num ++;
}
}
}
if( num + 1 == m) return ;
for(int i = 0; i < 4; i ++) {
vm.x = vn.x + xa[i];
vm.y = vn.y + ya[i];
if(!vis[vm.x][vm.y] && g[vm.x][vm.y] == '.'){
vis[vm.x][vm.y] = 1;
vm.dis = vn.dis + 1;
q.push(vm);
}
}
}
}
int main(){
while( cin >> n >> m){
clr(id, 0), clr(g, -1);
clr(dp, -1), clr(dis, -1);
for(int i = 1; i <= n; i ++) scanf("%s",g[i]+1);
for(int i = 0; i < m; i ++){
cin >> p[i].xs >> p[i].ys >> p[i].xe >> p[i].ye;
id[p[i].xs][p[i].ys] = 1;
}
for(int i = 0; i < m; i ++) {
dis[i][i] = 0;
bfs(i);
//for(int j = 0; j < m; j ++) cout << dis[i][j] << ' '; cout << endl;
}
/* 我自己写的超时的next_permutation 感觉时间复杂度应该在2^n * n^2 可还是超了
for(int i = 0; i < m; i ++) sun[i] = i;
int j, pre, nxt, ans, sum;
ans = -1;
do{
pre = sun[0];
sum = 0;
for(j = 1; j < m; j ++){
nxt = sun[j];
if( dis[pre][nxt] == -1) {
sum = -1;
break;
}
sum += dis[pre][nxt];
pre = nxt;
}
//for(int j = 0; j < m; j ++) cout << sun[j] << ' ' ; cout << endl;
//cout << sum << endl;
if(sum == -1) continue;
else {
if(ans == -1) ans = sum;
else ans = min(ans,sum);
}
}while(next_permutation(sun,sun+m));
cout << ans << endl;
*/
int all = (1<<m);
//dp[0][0] = 0;
for(int i = 0; i < m; i ++) dp[1<<i][i] = 0;
for(int i = 0; i <= all; i ++){
for(int j = 0; j < m; j ++){
if(dp[i][j] != -1 && i & (1<<j) ){
// cout << i << ' ' << j << endl;
for(int k = 0; k < m; k ++) if(!(i&1<<k) && dis[j][k] != -1){
int nxt = i | (1<<k);
if(dp[nxt][k] == -1) dp[nxt][k] = dp[i][j] + dis[j][k];
else dp[nxt][k] = min(dp[nxt][k], dp[i][j] + dis[j][k]);
}
}
}
}
//for(int i = 0; i < m; i ++) cout << dp[all-1][i] << ' '; cout << endl;
int ans = -1;
for(int i = 0; i < m; i ++){
if(dp[all-1][i] != -1) {
if(ans == -1) ans = dp[all-1][i];
else ans = min(ans, dp[all-1][i]);
}
}
cout << ans << endl;
}
return 0;
}