/**
* (1)求各點到源點的最小步數(BFS)
* (2)求各點到終點的最小步數(BFS)
* (3)如果點不是給定路徑上的點,那么:該點到源點的最小步數+該點到終點的最小步數<給定路徑的步數,否則給定路徑不是唯一最短的
* (4)如果兩相鄰點a、b之間存在墻,那么:a到源點的最小步數+1+b到終點的最小步數<=給定路徑的步數
* 或者 a到終點的最小步數+1+b到源點的最小步數<=給定路徑的步數,否則墻多余
* (5)如果存在點不可達,說明存在墻將該點封閉起來,可以證明墻至少有一塊多余
*/
#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct Grid
{
bool inpath; // 是否是路徑方格
bool uwal; // 是否有上墻
bool rwal; // 是否有右墻
int scnt; // 到源點步數
int dcnt; // 到終點步數
};
int main(int argc, char** argv)
{
bool ok;
int w, h, cnt, steps; // 1 <= w, h <= 100
string path;
Grid grid[100][100];
queue<pair<int, int> > q;
int t, x, y, desx, desy, x2, y2, i;
for (cin >> t; t > 0; --t)
{
// 初始化數據
cin >> w >> h;
for (y = 0; y < h; ++y)
for (x = 0; x < w; ++x)
{
grid[y][x].inpath = false;
grid[y][x].uwal = false;
grid[y][x].rwal = false;
grid[y][x].scnt = -1;
grid[y][x].dcnt = -1;
}
cin >> path;
x = 0, y = 0;
grid[0][0].inpath = true;
steps = path.size();
for (i = 0; i < steps; ++i)
{
switch(path[i])
{
case 'U': ++y; break;
case 'D': --y; break;
case 'L': --x; break;
case 'R': ++x; break;
}
grid[y][x].inpath = true;
}
desx = x, desy = y;
cin >> cnt;
for (i = 0; i < cnt; ++i)
{
cin >> x >> y >> x2 >> y2;
if (x == x2)
if (y + 1 == y2) grid[y][x].uwal = true;
else grid[y2][x].uwal = true;
else
if (x + 1 == x2) grid[y][x].rwal = true;
else grid[y][x2].rwal = true;
}
// 求各點到源點的最小步數(BFS)
q.push(make_pair(0, 0));
grid[0][0].scnt = 0;
while (!q.empty())
{
y = q.front().first, x = q.front().second;
if (y < h - 1 && grid[y][x].uwal == false && grid[y + 1][x].scnt == -1)
{
grid[y + 1][x].scnt = grid[y][x].scnt + 1;
q.push(make_pair(y + 1, x));
}
if (0 < y && grid[y - 1][x].uwal == false && grid[y - 1][x].scnt == -1)
{
grid[y - 1][x].scnt = grid[y][x].scnt + 1;
q.push(make_pair(y - 1, x));
}
if (0 < x && grid[y][x - 1].rwal == false && grid[y][x - 1].scnt == -1)
{
grid[y][x - 1].scnt = grid[y][x].scnt + 1;
q.push(make_pair(y, x - 1));
}
if (x < w - 1 && grid[y][x].rwal == false && grid[y][x + 1].scnt == -1)
{
grid[y][x + 1].scnt = grid[y][x].scnt + 1;
q.push(make_pair(y, x + 1));
}
q.pop();
}
// 求各點到終點的最小步數(BFS)
q.push(make_pair(desy, desx));
grid[desy][desx].dcnt = 0;
while (!q.empty())
{
y = q.front().first, x = q.front().second;
if (y < h - 1 && grid[y][x].uwal == false && grid[y + 1][x].dcnt == -1)
{
grid[y + 1][x].dcnt = grid[y][x].dcnt + 1;
q.push(make_pair(y + 1, x));
}
if (0 < y && grid[y - 1][x].uwal == false && grid[y - 1][x].dcnt == -1)
{
grid[y - 1][x].dcnt = grid[y][x].dcnt + 1;
q.push(make_pair(y - 1, x));
}
if (0 < x && grid[y][x - 1].rwal == false && grid[y][x - 1].dcnt == -1)
{
grid[y][x - 1].dcnt = grid[y][x].dcnt + 1;
q.push(make_pair(y, x - 1));
}
if (x < w - 1 && grid[y][x].rwal == false && grid[y][x + 1].dcnt == -1)
{
grid[y][x + 1].dcnt = grid[y][x].dcnt + 1;
q.push(make_pair(y, x + 1));
}
q.pop();
}
// 判斷路徑是否唯一最短,以及墻是否多余
ok = true;
for (y = 0; y < h && ok; ++y)
for (x = 0; x < w && ok; ++x)
{
if (grid[y][x].scnt == -1 || grid[y][x].dcnt == -1)
ok = false; // 是否有封閉區域
if (y < h - 1 && grid[y][x].uwal
&& grid[y][x].scnt + grid[y + 1][x].dcnt + 1 > steps
&& grid[y][x].dcnt + grid[y + 1][x].scnt + 1 > steps)
ok = false; // 是否上墻多余
if (x < w - 1 && grid[y][x].rwal
&& grid[y][x].scnt + grid[y][x + 1].dcnt + 1 > steps
&& grid[y][x].dcnt + grid[y][x + 1].scnt + 1 > steps)
ok = false; // 是否右墻多余
if (!grid[y][x].inpath && grid[y][x].scnt + grid[y][x].dcnt <= steps)
ok = false; // 是否存在更短路徑或另一最短路徑
}
if(ok) cout << "CORRECT" << endl;
else cout << "INCORRECT" << endl;
}
return 0;
}
* (1)求各點到源點的最小步數(BFS)
* (2)求各點到終點的最小步數(BFS)
* (3)如果點不是給定路徑上的點,那么:該點到源點的最小步數+該點到終點的最小步數<給定路徑的步數,否則給定路徑不是唯一最短的
* (4)如果兩相鄰點a、b之間存在墻,那么:a到源點的最小步數+1+b到終點的最小步數<=給定路徑的步數
* 或者 a到終點的最小步數+1+b到源點的最小步數<=給定路徑的步數,否則墻多余
* (5)如果存在點不可達,說明存在墻將該點封閉起來,可以證明墻至少有一塊多余
*/
#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct Grid
{
bool inpath; // 是否是路徑方格
bool uwal; // 是否有上墻
bool rwal; // 是否有右墻
int scnt; // 到源點步數
int dcnt; // 到終點步數
};
int main(int argc, char** argv)
{
bool ok;
int w, h, cnt, steps; // 1 <= w, h <= 100
string path;
Grid grid[100][100];
queue<pair<int, int> > q;
int t, x, y, desx, desy, x2, y2, i;
for (cin >> t; t > 0; --t)
{
// 初始化數據
cin >> w >> h;
for (y = 0; y < h; ++y)
for (x = 0; x < w; ++x)
{
grid[y][x].inpath = false;
grid[y][x].uwal = false;
grid[y][x].rwal = false;
grid[y][x].scnt = -1;
grid[y][x].dcnt = -1;
}
cin >> path;
x = 0, y = 0;
grid[0][0].inpath = true;
steps = path.size();
for (i = 0; i < steps; ++i)
{
switch(path[i])
{
case 'U': ++y; break;
case 'D': --y; break;
case 'L': --x; break;
case 'R': ++x; break;
}
grid[y][x].inpath = true;
}
desx = x, desy = y;
cin >> cnt;
for (i = 0; i < cnt; ++i)
{
cin >> x >> y >> x2 >> y2;
if (x == x2)
if (y + 1 == y2) grid[y][x].uwal = true;
else grid[y2][x].uwal = true;
else
if (x + 1 == x2) grid[y][x].rwal = true;
else grid[y][x2].rwal = true;
}
// 求各點到源點的最小步數(BFS)
q.push(make_pair(0, 0));
grid[0][0].scnt = 0;
while (!q.empty())
{
y = q.front().first, x = q.front().second;
if (y < h - 1 && grid[y][x].uwal == false && grid[y + 1][x].scnt == -1)
{
grid[y + 1][x].scnt = grid[y][x].scnt + 1;
q.push(make_pair(y + 1, x));
}
if (0 < y && grid[y - 1][x].uwal == false && grid[y - 1][x].scnt == -1)
{
grid[y - 1][x].scnt = grid[y][x].scnt + 1;
q.push(make_pair(y - 1, x));
}
if (0 < x && grid[y][x - 1].rwal == false && grid[y][x - 1].scnt == -1)
{
grid[y][x - 1].scnt = grid[y][x].scnt + 1;
q.push(make_pair(y, x - 1));
}
if (x < w - 1 && grid[y][x].rwal == false && grid[y][x + 1].scnt == -1)
{
grid[y][x + 1].scnt = grid[y][x].scnt + 1;
q.push(make_pair(y, x + 1));
}
q.pop();
}
// 求各點到終點的最小步數(BFS)
q.push(make_pair(desy, desx));
grid[desy][desx].dcnt = 0;
while (!q.empty())
{
y = q.front().first, x = q.front().second;
if (y < h - 1 && grid[y][x].uwal == false && grid[y + 1][x].dcnt == -1)
{
grid[y + 1][x].dcnt = grid[y][x].dcnt + 1;
q.push(make_pair(y + 1, x));
}
if (0 < y && grid[y - 1][x].uwal == false && grid[y - 1][x].dcnt == -1)
{
grid[y - 1][x].dcnt = grid[y][x].dcnt + 1;
q.push(make_pair(y - 1, x));
}
if (0 < x && grid[y][x - 1].rwal == false && grid[y][x - 1].dcnt == -1)
{
grid[y][x - 1].dcnt = grid[y][x].dcnt + 1;
q.push(make_pair(y, x - 1));
}
if (x < w - 1 && grid[y][x].rwal == false && grid[y][x + 1].dcnt == -1)
{
grid[y][x + 1].dcnt = grid[y][x].dcnt + 1;
q.push(make_pair(y, x + 1));
}
q.pop();
}
// 判斷路徑是否唯一最短,以及墻是否多余
ok = true;
for (y = 0; y < h && ok; ++y)
for (x = 0; x < w && ok; ++x)
{
if (grid[y][x].scnt == -1 || grid[y][x].dcnt == -1)
ok = false; // 是否有封閉區域
if (y < h - 1 && grid[y][x].uwal
&& grid[y][x].scnt + grid[y + 1][x].dcnt + 1 > steps
&& grid[y][x].dcnt + grid[y + 1][x].scnt + 1 > steps)
ok = false; // 是否上墻多余
if (x < w - 1 && grid[y][x].rwal
&& grid[y][x].scnt + grid[y][x + 1].dcnt + 1 > steps
&& grid[y][x].dcnt + grid[y][x + 1].scnt + 1 > steps)
ok = false; // 是否右墻多余
if (!grid[y][x].inpath && grid[y][x].scnt + grid[y][x].dcnt <= steps)
ok = false; // 是否存在更短路徑或另一最短路徑
}
if(ok) cout << "CORRECT" << endl;
else cout << "INCORRECT" << endl;
}
return 0;
}