# Untitled

unknown
plain_text
25 days ago
5.3 kB
1
Indexable
Never
```//The Knight
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#define MAX_QUEUE 1000000
template<typename T>
class Queue {
T Q[MAX_QUEUE];
int front;
int rear;
public:
Queue()
{
front = rear = -1;
}
bool isEmpty()
{
return front == -1;
}
bool isFull()
{
return front == 0 && rear == MAX_QUEUE - 1;
}
int size()
{
if (isEmpty())
return 0;
else return rear - front + 1;
}
void enQueue(T data)
{
if (!isFull())
{
if (front == -1) front++;
rear++;
Q[rear] = data;
}
}
T deQueue()
{
T element;
if (!isEmpty())
{
element = Q[front];
if (front >= rear)
{
reset();
}
else front++;
return element;
}
}
void reset()
{
front = rear = -1;
}
{
return Q[front];
}
T tail()
{
return Q[rear];
}
};
#define MAX 100
#define MAX_P 20
#define INF 10000000
int M, N, Point, step, min_step;
int map[MAX][MAX];
int visited[MAX][MAX];
int visited_point[MAX_P];
int dr[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dc[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int R[MAX_P];
int C[MAX_P];
Queue<int> Q = Queue<int>();
void resetVisited()
{
for(int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
{
visited[i][j] = 0;
}
}

int BFS(int s, int e)
{
int nr, nc, cr, cc;
Q.reset();
resetVisited();
Q.enQueue(R[s]);
Q.enQueue(C[s]);
visited[R[s]][C[s]] = 1;
while (!Q.isEmpty())
{
cr = Q.deQueue();
cc = Q.deQueue();
for (int i = 0; i < 8; i++)
{
nr = cr + dr[i];
nc = cc + dc[i];
if (nr >= 0 && nr < M && nc >= 0 && nc < N && visited[nr][nc] == 0)
{
Q.enQueue(nr);
Q.enQueue(nc);
visited[nr][nc] = visited[cr][cc] + 1;
if (nr == R[e] && nc == C[e])
return visited[nr][nc] - 1;
}
}
}
return -1;
}
void backtrack(int k, int prev)
{
if (step >= min_step)
return;
if (k == Point)
{
min_step = step < min_step ? step : min_step;
return;
}
for (int i = 1; i < Point; i++)
{
if (visited_point[i] == 0)
{
visited_point[i] = 1;
backtrack(k + 1, i);
visited_point[i] = 0;
}
}
}
int main()
{
int tc, T;
freopen("input.txt", "r", stdin);
cin >> T;
for (tc = 1; tc <= T; tc++)
{
cin >> M >> N;
Point = 1;
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
cin >> map[i][j];
if (map[i][j] == 3)
{
R[0] = i;
C[0] = j;
}
if (map[i][j] == 1)
{
R[Point] = i;
C[Point] = j;
Point++;
}
}
}
for (int i = 0; i < Point; i++)
{
visited_point[i] = 0;
for (int j = i; j < Point; j++)
{
if (j == i)
else
{
}
}
}
step = 0; min_step = INF;
backtrack(1, 0);
cout << "Case #" << tc << endl;
cout << min_step << endl;
}
return 0;
}

// The crazy King
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define MAX_QUEUE 1000000
template<typename T>
class Queue {
T Q[MAX_QUEUE];
int front;
int rear;
public:
Queue()
{
front = rear = -1;
}
bool isEmpty()
{
return front == -1;
}
bool isFull()
{
return front == 0 && rear == MAX_QUEUE - 1;
}
int size()
{
if (isEmpty())
return 0;
else return rear - front + 1;
}
void enQueue(T data)
{
if (!isFull())
{
if (front == -1) front++;
rear++;
Q[rear] = data;
}
}
T deQueue()
{
T element;
if (!isEmpty())
{
element = Q[front];
if (front >= rear)
{
reset();
}
else front++;
return element;
}
}
void reset()
{
front = rear = -1;
}
{
return Q[front];
}
T tail()
{
return Q[rear];
}
};
using namespace std;
#define MAX 105
int M, N, sr, sc, er, ec, ans;
char map[MAX][MAX];
int visited[MAX][MAX];
int drH[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int dcH[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int drK[8] = { 0, 0, 1, -1, -1, -1, 1, 1 };
int dcK[8] = { 1, -1, 0, 0, -1, 1, -1, 1 };
Queue<int> Q = Queue<int>();
void marking(int r, int c)
{
int nr, nc;
visited[r][c] = -1;
for (int i = 0; i < 8; i++)
{
nr = r + drH[i];
nc = c + dcH[i];
if (nr >= 0 && nr < M && nc >= 0 && nc < N)
visited[nr][nc] = -1;
}
}
int main()
{
int tc, T, cr, cc, nr, nc;
freopen("input.txt", "r", stdin);
cin >> T;
for (tc = 1; tc <= T; tc++)
{
cin >> M >> N;
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
visited[i][j] = 0;
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
cin >> map[i][j];
if (map[i][j] == 'A')
{
sr = i;
sc = j;
}
else if (map[i][j] == 'B')
{
er = i;
ec = j;
}
else if (map[i][j] == 'Z')
marking(i, j);
}
}
ans = -1;
Q.reset();
Q.enQueue(sr);
Q.enQueue(sc);
visited[sr][sc] = 1;
visited[er][ec] = 0;
while (!Q.isEmpty())
{
cr = Q.deQueue();
cc = Q.deQueue();
for (int i = 0; i < 8; i++)
{
nr = cr + drK[i];
nc = cc + dcK[i];
if (nr >= 0 && nr < M && nc >= 0 && nc < N && visited[nr][nc] == 0)
{
Q.enQueue(nr);
Q.enQueue(nc);
visited[nr][nc] = visited[cr][cc] + 1;

if (nr == er && nc == ec)
{
ans = visited[nr][nc] - 1;
goto end;
}
}
}
}
end:
cout << ans << endl;
}
return 0;
}```