[UVA][TSP] 11405 - Can U Win?
Can U Win?
| Can U Win? |
You are playing Chess with your little sister. Unfortunately She is too smart for you. You are about to lose with only a King and a Knight. Your sister is mad about `panju muttai' (also known as cotton candy). `panju muttai'-seller has just come and ur sister went out to have her `panju muttai'. You are a honest person and have promised yourself to be honest. But you are also wily. You pacify your conscience that your sister is passing her moves (yes, that version of chess allows you to pass your move) and make `legal' moves !!
You found that, due to unknown reasons, your sister will lose if and only if she loses all her pawns. you also found that you cannot make moves which kills coins other than pawns when she is away. Can U Ensure your Win making not more than n legal (or illegal?) moves before your sister returns?
The Coins are represented as follows:
- Your King = `K'
- Your Knight = `k'
- Enemy Pawns = `P'
- Other Enemy Pieces = `p'
- Empty Location = `.'
Constraints
- Your King can be moved only when your sister is present
- Knight should make only valid chess moves (ie. `L' shaped moves)
- There will be 1 `K', 1 `k', 0 to 8 `P's, 0 to 8 `p's in the board
Input
The first line has an integer t
, giving the number of test cases.
1 < t
100
.
Each test case described as follows:
First line gives value of `n ' (the number of moves after which the sister will come).
Next 8 lines contain 8 characters each describing the board.
A Blank line comes before each test case.
Output
For Each test case,
In a single line, print `Yes' if you can win making not more than n moves or `No' if you cannot.
Sample Input
2 3 ...pP... ..P..k.K p.....p. ...p.... ...p.... ........ .p...... ........ 2 .....kp. ........ ...Kp... .P...p.. .p.....p ...p.... ........ .p......
Sample Output
Yes No
題目描述：
跟妹妹玩西洋棋，由於妹妹非常喜愛棉花糖，暫時離開遊戲。
目標使用騎士，將妹妹的小兵都殺掉，並且途中不能碰到其他棋子。
這麼聰明的妹妹哪裡找，殺到只剩下國王和一個騎士 orz。
題目解法：
加上騎士本身是 9 個點的 TSP，但這裡求的 TSP 不用繞回原點。
查看能不能在 n 步內完成目標。
#include <stdio.h>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
char g[10][10];
int ng[10][10];
int dist[10][10], dp[1<<10][10];
void bfs(int x, int y) {
queue<int> X, Y;
int i, j, tx, ty;
int dx[] = {1,1,-1,-1,2,2,-2,-2};
int dy[] = {2,-2,2,-2,1,-1,1,-1};
int used[8][8] = {};
X.push(x), Y.push(y);
int st = ng[x][y];
while(!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
for(i = 0; i < 8; i++) {
tx = x+dx[i], ty = y+dy[i];
if(tx < 0 || ty < 0 || tx >= 8 || ty >= 8)
continue;
if(g[tx][ty] == 'K' || g[tx][ty] == 'p')
continue;
if(used[tx][ty] == 0) {
used[tx][ty] = used[x][y]+1;
X.push(tx), Y.push(ty);
if(g[tx][ty] == 'P')
dist[st][ng[tx][ty]] = used[x][y]+1;
}
}
}
}
int dfs(int state, int last, int n) {
int &ret = dp[state][last];
if(ret != -1) return ret;
if(state == 0)
return 0;
ret = 0xfffffff;
int i;
for(i = 0; i < n; i++) {
if((state>>i)&1) {
ret = min(ret, dfs(state^(1<<i), i, n)+dist[last][i]);
}
}
return ret;
}
int main() {
int testcase, n;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < 8; i++)
scanf("%s", &g[i]);
int m = 1;
for(i = 0; i < 8; i++) {
for(j = 0; j < 8; j++) {
if(g[i][j] == 'k') {
ng[i][j] = 0;
g[i][j] = 'P';
}else if(g[i][j] == 'P')
ng[i][j] = m++;
}
}
for(i = 0; i < m; i++)
for(j = 0; j < m; j++)
dist[i][j] = 0xfffffff;
for(i = 0; i < 8; i++) {
for(j = 0; j < 8; j++) {
if(g[i][j] == 'P')
bfs(i, j);
}
}
memset(dp, -1, sizeof(dp));
int ret = dfs((1<<m)-1-1, 0, m);
if(m == 1) ret = 0;
if(ret <= n)
puts("Yes");
else
puts("No");
}
return 0;
}