8 条题解

  • 2
    @ 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
      @ 2025-3-30 21:38:24 
      #include <iostream>
#include <string>
#include <vector>
using namespace std;

const string target = "tencent";
int n, m;
vector<vector<char>> matrix;
int directions[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int ans = 0;

void dfs(int x, int y, int step) {
    if (step == 6) {
        ans++;
        return;
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
        matrix[nx][ny] == target[step + 1]) {
            dfs(nx, ny, step + 1);
        }
    }
}

int main() {
    cin >> n >> m;
    matrix.resize(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 't') {
                dfs(i, j, 0);
            }
        }
    }
    cout << ans << endl;
    return 0;
}
      • 0
        @ 2025-3-30 15:02:56 
        #include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,ans;
char g[N][N];
string target="tencent";
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int x,int y,int pos){
    if(pos==6){
        ans++;
        return;
    }
    for(int i=0;i<4;i++){
        int a=x+dx[i],b=y+dy[i];
        if(g[a][b]==target[pos+1]){
            dfs(a,b,pos+1);
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i][j]=='t'){
                dfs(i,j,0);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
//tencent
        • 0
          @ 2025-3-15 23:04:44

          DFS

          #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e3 + 5;
const int INF = 0x3f3f3f3f;
char g[N][N];
int vis[N][N];
int n, m ,ans;

int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};

string s = "tencent";
void dfs(int x,int y,int c) {
    if(x < 1 || x > n || y < 1 || y > m) return;
    if(g[x][y] != s[c]) return;
    if(c == 6 && g[x][y] == s[6]) {
        ans++;
        return;
    }
    for(int i = 0;i < 4;i++){
        int x1 = x + dx[i];int y1 = y + dy[i];
        if(vis[x1][y1]) continue;
        vis[x1][y1] = 1;
        dfs(x1,y1,c + 1);
        vis[x1][y1] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            cin >> g[i][j];
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(g[i][j] == 't')
                dfs(i,j,0);
        }    
    }
    cout << ans << endl;
    return 0;
}
          • 0
            @ 2025-2-10 10:57:37 
            #include<bits/stdc++.h>
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);
        }
    }
}
int main()
{
    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;
    return 0;
}
            • 0
              @ 2025-1-18 17:21:23 
              // https://dashoj.com/p/81
// tencent
#include <bits/stdc++.h>

#define N 1010
using namespace std;
string str = "tencent";
int n, m, ans = 0, dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
char g[N][N];

void dfs(int x, int y, int cnt) {
	if (cnt == 7) {
		ans++;
		return;
	}
	char c = str[cnt];
	for (int i = 0; i < 4; i++) {
		int vx = x + dx[i], vy = y + dy[i];
		if (vx >= 1 && vx <= n && vy >= 1 && vy <= m && g[vx][vy] == c) dfs(vx, vy, cnt + 1);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> g[i][j];
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (g[i][j] == 't') dfs(i, j, 1);
	cout << ans << endl;
	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
                  难度
                  6
                  标签
                  递交数
                  309
                  已通过
                  84
                  上传者
                  1. 兼容模式
                  2. © 2024-2028 Dashcoding
                  3. 粤ICP备2024204050号-1
                  4. Powered by Hydro