玲珑OJ 1082：XJT Loves Boggle（爆搜）-白红宇

玲珑OJ 1082：XJT Loves Boggle（爆搜）

阅读量：5053 次

发布时间：2019-06-12

本文共 1671 字，大约阅读时间需要 5 分钟。

题意：给出的单词要在3*3矩阵里面相邻连续（相邻包括对角），如果不行就输出0，如果可行就输出对应长度的分数。

思路：爆搜，但是写砸了。处理一次状态的时候把vis[i][j]设成1，然后DFS。DFS完之后还要把vis[i][j]改成0，否则就会只搜一条路径了。QAQ。正解貌似是枚举所有的可行字符串丢到set里面。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             10 #include 
              
               11 #include 
               
                12 using namespace std;13 typedef long long LL;14 #define N 10001015 #define INF 0x3f3f3f3f16 17 char mp[100][100], s[100];18 int vis[100][100], dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[] = { 1, 0, -1, 1, -1, 1, 0, -1}, flag;19 int mm[] = { 0, 0, 0, 1, 1, 2, 3, 5, 11, 11};20 21 bool check(int x, int y, char c) {22 if(0 <= x && x < 3 && 0 <= y && y < 3 && mp[x][y] == c && !vis[x][y]) return true;23 return false;24 }25 26 void DFS(int x, int y, int now, int len) {27 if(now >= len - 1) { flag = 1; return ; }28 for(int i = 0; i < 8; i++) {29 int nx = dx[i] + x, ny = dy[i] + y;30 if(check(nx, ny, s[now+1])) {31 vis[nx][ny] = 1;32 DFS(nx, ny, now + 1, len);33 vis[nx][ny] = 0;34 }35 }36 }37 38 int main()39 {40 int t;41 scanf("%d", &t);42 for(int cas = 1; cas <= t; cas++) {43 for(int i = 0; i < 3; i++) scanf("%s", mp[i]);44 int q; scanf("%d", &q);45 printf("Case #%d:\n", cas);46 while(q--) {47 scanf("%s", s);48 int len = strlen(s); flag = 0;49 if(len >= 3)50 for(int i = 0; i < 3 && !flag; i++) {51 for(int j = 0; j < 3 && !flag; j++) {52 if(mp[i][j] == s[0]) {53 memset(vis, 0, sizeof(vis));54 vis[i][j] = 1;55 DFS(i, j, 0, len);56 }57 }58 }59 printf("%d\n", flag ? mm[len] : 0);60 }61 }62 return 0;63 }

转载于:https://www.cnblogs.com/fightfordream/p/6285489.html

你可能感兴趣的文章