本文共 1235 字,大约阅读时间需要 4 分钟。
这道题是普通的DFS,不需要优化就可以通过。
/* ID: thestor1 LANG: C++ TASK: poj1154 */#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;const int MAXR = 20;// There is '\0' in the endconst int MAXC = 20 + 1;int neighbors[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};void dfs(char board[][MAXC], int r, int c, const int R, const int C, bool visited[], int p, int &maxp) { int i = board[r][c] - 'A'; if (visited[i]) { return; } visited[i] = true; p++; if (p > maxp) { maxp = p; } for (int d = 0; d < 4; ++d) { int nr = r + neighbors[d][0]; int nc = c + neighbors[d][1]; if (0 <= nr && nr < R && 0 <= nc && nc < C) { dfs(board, nr, nc, R, C, visited, p, maxp); } } visited[i] = false;}int main(){ char board[MAXR][MAXC]; int R, C; scanf("%d%d", &R, &C); for (int r = 0; r < R; ++r) { scanf("%s", board[r]); } // printf("[debug]board:\n"); // for (int r = 0; r < R; ++r) { // printf("[%s]\n", board[r]); // } bool visited[26]; for (int i = 0; i < 26; ++i) { visited[i] = false; } int maxp = 0; dfs(board, 0, 0, R, C, visited, 0, maxp); printf("%d\n", maxp); return 0;}
转载地址:http://wtxli.baihongyu.com/