3 条题解

  • 0
    @ 2024-4-12 21:04:40

    DFS

    #include <iostream>
    
    using namespace std;
    
    const int N = 1010;
    
    char s[] = "tencent";
    
    int n, m;
    char d[N][N];
    bool st[N][N];
    int ans;
    
    int dx[] = { -1, 0, 1, 0 };
    int dy[] = { 0, -1, 0, 1 };
    
    void dfs(int x, int y, int u)
    {
    	if (u == 6)
    	{
    		ans++;
    		return;
    	}
    
    	for (int i = 0; i < 4; i++)
    	{
    		int nx = x + dx[i], ny = y + dy[i];
    		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && d[nx][ny] == s[u + 1])
    			dfs(nx, ny, u + 1);
    	}
    }
    
    void solve()
    {
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= m; j++)
    			cin >> d[i][j];
    
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= m; j++)
    			if (d[i][j] == 't')
    				dfs(i, j, 0);
    		
    	cout << ans << endl;
    }
    
    int main()
    {
    	solve();
    	return 0;
    }
    
    • 0
      @ 2024-4-9 12:00:07
      #include<bits/stdc++.h>
      using namespace std;
      char Map[1010][1010];
      int n, m, ans;
      int d[4][2] =
      {
          {-1,0},
          {1,0},
          {0,-1},
          {0,1}
      };
      struct point
      {
          int x;
          int y;
          int cnt;
          string str;
      };
      
      void bfs(int x, int y)
      {
          queue<point> que;//重新构造队列
      
          point start;
          start.x = x, start.y = y, start.cnt = 0;
          start.str = Map[x][y];
          que.push(start);
          while (!que.empty())
          {
              if (que.front().cnt == 6 && que.front().str == "tencent")
              {
                  ans++;
               
              }
              else if (que.front().cnt > 6) break;
              for (int i = 0; i < 4; i++)
              {
                  int tx = que.front().x + d[i][0], ty = que.front().y + d[i][1];
                  if (tx >= 1 && tx <= n && ty >= 1 && ty <= m)
                  {
                      point temp;
                      temp.x = tx;
                      temp.y = ty;
                      temp.cnt = que.front().cnt + 1;
                      temp.str = que.front().str + Map[tx][ty];
                      que.push(temp);
                  }
              }
              que.pop();
          }
      }
      
      int main()
      {
          cin >> n >> m;
          for (int i = 1; i <= n; i++)
              for (int j = 1; j <= m; j++)
                  cin >> Map[i][j];
          for (int i = 1; i <= n; i++)
          {
              for (int j = 1; j <= m; j++)
              {
                  bfs(i, j);            
              }
          }
          cout << ans;
          return 0;
      }
      
      • 0
        @ 2024-4-7 10:25:02

        import java.io.*;

        public class Main { public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); public static int n; public static int m; public static String[][] map; public static long cnt = 0; public static boolean[][] isuse; public static String[] t = { "t", "e", "n", "c", "e", "n", "t" }; public static int[][] way = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

        public static void main(String[] args) throws IOException {
        	// TODO Auto-generated method stub
        	String[] s = in.readLine().split(" ");
        	n = Integer.parseInt(s[0]);
        	m = Integer.parseInt(s[1]);
        	map = new String[n][m];
        	isuse = new boolean[n][m];
        	for (int i = 0; i < n; i++) {
        		map[i] = in.readLine().split("");
        	}
        	for (int i = 0; i < n; i++) {
        		for (int j = 0; j < m; j++) {
        			if (map[i][j].equals("t")) {//剪枝,从t开始走
        				dfs(i, j, 1, map[i][j]);
        			}
        		}
        	}
        	System.out.println(cnt);
        }
        
        public static void dfs(int x, int y, int len, String ans) {
        	if (ans.equals("tencent")) {
        		cnt++;
        		return;
        	}
        	if (len > 6)//剪枝
        		return;
        	for (int i = 0; i < 4; i++) {//枚举四个方向
        		int xx = x + way[i][0];
        		int yy = y + way[i][1];
        		//剪枝,下一步要走的和期望要得到的字符一样才走
        		if (check(xx, yy) && map[xx][yy].equals(t[len])) {
        			isuse[xx][yy] = true;//走过就不走了
        			dfs(xx, yy, len + 1, ans + map[xx][yy]);
        			isuse[xx][yy] = false;//回溯
        		}
        	}
        }
        
        public static boolean check(int x, int y) {//判断是否在边界内,并且可走
        	return x >= 0 && x < n && y >= 0 && y < m && isuse[x][y] == false;
        }
        

        }

        • 1

        信息

        ID
        81
        时间
        1000ms
        内存
        256MiB
        难度
        7
        标签
        递交数
        100
        已通过
        21
        上传者