POJ_3194_Equidivisions

TheAlgorithmArt

于 2010-08-28 18:26:00 发布

阅读量708

点赞数

分类专栏： POJ中的搜索 POJ 文章标签： include

本文链接：https://blog.csdn.net/TheAlgorithmArt/article/details/5846454

版权

POJ 同时被 2 个专栏收录

10 篇文章

订阅专栏

POJ中的搜索

2 篇文章

订阅专栏

本文介绍了一种基于深度优先搜索（DFS）的迷宫遍历算法实现，通过递归方式探索所有可能路径，并标记已访问节点避免重复访问。文章详细展示了如何利用邻接矩阵表示迷宫状态，通过方向数组实现上下左右四个方向的移动判断，同时采用辅助函数验证位置的有效性。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include <iostream> using namespace std; int N, ans; int map[101][101]; int visit[101][101]; int step[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; int color[101]; bool Check(int x, int y) { if (x >= N || x < 0 || y >= N || y < 0) return false; return true; } void DFS(int CurX, int CurY) { ans++; visit[CurX][CurY] = 1; color[map[CurX][CurY]] = 1; for (int i = 0; i < 4; i++) { int x = CurX+step[i][0]; int y = CurY+step[i][1]; if (Check(x, y) == false || visit[x][y] == 1) continue; if (map[CurX][CurY] == map[x][y] || color[map[x][y]] == 0) { DFS(x, y); } } } int main() { freopen("test.txt", "r", stdin); while (cin>>N && N !=0) { int index = 1; ans = 0; memset(map, 0, sizeof(map)); memset(visit, 0, sizeof(visit)); memset(color, 0, sizeof(color)); for (int i = 0; i < N-1; i++) { for (int j = 0; j < N; j++) { int a, b; cin>>a>>b; map[a-1][b-1] = index; } index++; } DFS(0, 0); if (ans == N*N) cout<<"good"<<endl; else cout<<"wrong"<<endl; } return 0; }