POJ 1024 Tester Program
[cpp]/*
WA
主要思路:
首先DFS建立层次图。
然后判断,路径是否唯一,墙壁是否重复。
*/
#include <iostream>
//#define TEST
using namespace std;
const int nMax = 105;
const int mMax = 10100;
int dis_s[nMax][nMax], dis_e[nMax][nMax];
char s[mMax];
struct Node
{
int x1, y1;
int x2, y2;
Node(){}
Node(int x1, int y1, int x2, int y2):x1(x1), y1(y1), x2(x2), y2(y2){}
}node[2 * mMax];
int ind;
int visit[nMax][nMax];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int W, H;
int n;
int step;
struct Queue
{
int x, y;
Queue(){}
Queue(int x, int y):x(x), y(y){}
}queue[mMax];
bool isExist(int a, int b, int x, int y)//判断(a,b)(x,y)之间是否存在墙
{
for(int i = 0; i < ind; ++ i)
{
if(node[i].x1 == a && node[i].y1 == b && node[i].x2 == x && node[i].y2 == y)
return 1;
}
return 0;
}
void bfs(int a, int b, int dis[][nMax])//建层次图,原来出错,BFS,需要用到队列
{
int front, rear;
front = rear = 0;
queue[front ++] = Queue(a, b);
while(rear < front)
{
int x = queue[rear].x;
int y = queue[rear].y;
rear ++;
for(int i = 0; i < 4; ++ i)
{
int _x = x + dir[i][0];
int _y = y + dir[i][1];
if(_x >= 0 && _x < W && _y >= 0 && _y < H)
{
if(!isExist(x, y, _x, _y) && dis[_x][_y] == -1)
{
dis[_x][_y] = dis[x][y] + 1;
queue[front ++] = Queue(_x, _y);
}
}
}
}
}
bool isUnique()//判断路径是否唯一
{
for(int i = 0; i < W; ++ i)
{
for(int j = 0; j < H; ++ j)
{
if(!visit[i][j])
{
if(dis_s[i][j] + dis_e[i][j] <= step)//空余位置节点到起始点和终点距离之和小于等于step
return 0;
}
}
}
return 1;
}
bool isRepeat()
{
for(int i = 0; i < n; ++ i)
{
if(dis_s[node[i].x1][node[i].y1] + dis_e[node[i].x2][node[i].y2] >= step && dis_e[node[i].x1][node[i].y1] + dis_s[node[i].x2][node[i].y2] >= step)
//墙壁两侧到起始点和终点的距离之和大于等于step
return 1;
}
return 0;
}
int main()
{
freopen("e://data.txt", "r", stdin);
//freopen("e://dataout.txt", "w", stdout);
int T;
scanf("%d", &T);
while(T --)
{
int flag = 0;
scanf("%d%d", &H, &W);
scanf("%s", s);
scanf("%d", &n);
int x1, y1, x2, y2;
ind = 0;
for(int i = 0; i < n; ++ i)
{
scanf("%d%d%d%d", &y1, &x1, &y2, &x2);
node[ind ++] = Node(x1, y1, x2, y2);
node[ind ++] = Node(x2, y2, x1, y1);
}
int a, b;
a = b = 0;
step = strlen(s);
memset(visit, 0, sizeof(visit));
visit[0][0] = 1;
for(int i = 0; i < step; ++ i)
{
int x1, y1;
x1 = a;
y1 = b;
if(s[i] == 'L')
b --;
else if(s[i] == 'R')
补充:软件开发 , C++ ,