3 条题解
-
0
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
#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
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
- 上传者