【NEEPU OJ】1039--Attack on Tanks 2 - Hard Version

描述

There is a battle between country A and country B. The army of country A attacked into a fortress of country B by tanks. The army of country A wants to kill all enemies in the fortress. However, there are some walls in the fortress. Equipped with tanks, the army can break walls! To simplify the problem, let’s regard the fortress as a matrix with length of n and height of m.

|------------>x
| O O O O O
| O X X C O
| O X C O O
| O O O O O
V
y

In this case, n is 5 and m is 4. X means that there is a wall in the position. C means that there is an enemy in the position. In one step, the tank can move up, down, left or right in the map. Be attention: Although we can break wall, we can’t break wall continuously. For example, if we create a coordinate system as the picture, when we had already broken a wall in (x=2,y=2) , we CANNOT break the wall (x=3,y=2) in the next move. Because of the wall fragments, if a wall has been broken, you should still regard it as a wall when you move to it again. If the tank moves onto an enemy, the enemy will be killed.

The tank is positioned at the left-top corner (x=1,y=1) first. It is guaranteed that the initial position is always empty. Given the map of the fortress and an order to kill the enemies, can you tell the commander of Country A’s army, what the minimum step count is?

输入

There are multiple test cases. There will be a single number T(1<=T<=10) in the input indicating the test cases number. Then follows T test cases. In the beginning of each test case, there will be two integers n(2<=n<=100) and m(2<=m<=100), as described above. Then follows a n×m matrix, only containing character ‘O’, ‘X’, ‘C’, indicating empty room, a wall, and an enemy. Each character will be separated by a white space. Next line contains an integer K(1<=k<=5000), indicating the enemy count. Then follows K lines. In the i-th line, there are two integers x_i and y_i, indicating the coordinate of the enemy, which should be i-th killed.

输出

If all the enemy could be killed, output the minimum steps they need. Otherwise, output a single word ‘impossible’.

输入样例 1

1
5 4
O O O O O
O X X C O
O X C O O
O O O O O
2
3 3
4 2

输出样例 1

6

来源

NEEPU 13th ACM

---

代码

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int matrix[110][110];
int vis[110][110];
int xx, yy, res, c;

struct node{
    int x, y;
}start, over;

bool judgeX(int ty, int tx, int flag){
    if(matrix[ty][tx] == 'X' && flag == 1) return 0;
    else return 1;
}

void bfs(){
    queue<node> q;
    q.push(start);
    int i1, flag, quit = 0;
    vis[start.y][start.x] = 0;
    if(over.y == start.y && over.x == start.x){
        c--;
        quit = 1;
    }
    while(!q.empty() && quit == 0){
        node t1 = q.front();
        q.pop();
        flag = 0;
        if(matrix[t1.y][t1.x] == 'X') flag = 1;
        for(i1 = 0; i1 < 4; i1++){
            node t2;
            t2.x = t1.x + dx[i1];
            t2.y = t1.y + dy[i1];
            if(t2.x > 0 && t2.x <= xx && t2.y > 0 && t2.y <= yy && !vis[t2.y][t2.x] && judgeX(t2.y, t2.x, flag)){
                vis[t2.y][t2.x] = vis[t1.y][t1.x] + 1;
                q.push(t2);
                if(t2.y == over.y && t2.x == over.x){
                    c--;
                    res += vis[t2.y][t2.x];
                    start = over;
                    quit = 1;
                    q.pop();
                    break;
                }
            }
        }
    }
}

int main(){
    int n, k, i, j;
    scanf("%d", &n);
    while(n--){
        res = c = 0;
        start.x = start.y = over.x = over.y = 1;
        memset(matrix, 0, sizeof(matrix));
        scanf("%d %d%*c", &xx, &yy);
        for(i = 1; i <= yy; i++){
            for(j = 1; j <= xx; j++){
                scanf("%c%*c", &matrix[i][j]);
                if(matrix[i][j] == 'C') c++;
            }
        }
        scanf("%d", &k);
        while(k--){
            scanf("%d %d", &over.x, &over.y);
            memset(vis, 0, sizeof(vis));
            bfs();
        }
        if(c == 0) printf("%d\n", res);
        else printf("impossible\n");
    }
    return 0;
}