http://poj.org/problem?id=1024
#include <stdio.h>
#include <string.h>
struct pos
{
int len[2];
int used;
int r;
int u;
}p[20][20];
int num, wallNum, w, h, Dx, Dy, minPath;
void DFS(int x, int y, int len, int flag)
{
if (len >= p[x][y].len[flag] && p[x][y].len[flag]!=0)
return;
if (x+y!=0 && (x!=Dx||y!=Dy))
p[x][y].len[flag] = len;
len++;
if (p[x][y].r==0 && x+1<w)
DFS(x+1, y, len, flag);
if (p[x][y].u==0 && y+1<h)
DFS(x, y+1, len, flag);
if (x-1>=0 && p[x-1][y].r==0)
DFS(x-1, y, len, flag);
if (y-1>=0 && p[x][y-1].u==0)
DFS(x, y-1, len, flag);
}
int judge()
{
int i, j;
for (i=0; i<w; i++)
for (j=0; j<h; j++)
{
if (p[i][j].used==0 && p[i][j].len[0]+p[i][j].len[1]<=minPath)
return 0;
if (p[i][j].r==1 && i+1<w && p[i][j].len[0]+p[i+1][j].len[1]+1>minPath && p[i][j].len[1]+p[i+1][j].len[0]+1>minPath)
return 0;
if (p[i][j].u==1 && j+1<h && p[i][j].len[0]+p[i][j+1].len[1]+1>minPath && p[i][j].len[1]+p[i][j+1].len[0]+1>minPath)
return 0;
}
return 1;
}
int main()
{
int x, y, x1, y1, x2, y2;
char c;
scanf("%d", &num);
while (num--)
{
memset(p, 0, sizeof(p));
scanf("%d %dn", &w, &h);
p[0][0].used = 1;
Dx = Dy = minPath = 0;
while ((c=getchar())!='n' && c!=EOF)
{
if (c == 'U')
p[Dx][++Dy].used = 1;
else if (c == 'D')
p[Dx][--Dy].used = 1;
else if (c == 'L')
p[--Dx][Dy].used = 1;
else if (c == 'R')
p[++Dx][Dy].used = 1;
minPath++;
}
scanf("%d", &wallNum);
while (wallNum--)
{
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
x = x1 - x2;
y = y1 - y2;
if (x==0 && y==1)
p[x2][y2].u = 1;
else if (x==0 && y==-1)
p[x1][y1].u = 1;
else if (x==1 && y==0)
p[x2][y2].r = 1;
else if (x==-1 && y==0)
p[x1][y1].r = 1;
}
DFS(0, 0, 0, 0);
DFS(Dx, Dy, 0, 1);
if(judge())
printf("CORRECTn");
else
printf("INCORRECTn");
}
return 0;
}