2022.11.30每日刷题打卡

 Fire Net HDU - 1045 

Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.

A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.

Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.

The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.

The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.

Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration. 

Input

The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a '.' indicating an open space and an uppercase 'X' indicating a wall. There are no spaces in the input file.

Output

For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration.

Sample

4 
.X.. 
.... 
XX.. 
.... 
2 
XX 
.X 
3 
.X. 
X.X 
.X. 
3 
... 
.XX 
.XX 
4 
.... 
.... 
.... 
.... 
0 

5 
1 
5 
2 
4 

原题链接：传送门

题意：给出一张图，图中'X'表示wall,'.'表示空地,可以放置blockhouse同一条直线上只能有一个blockhouse，除非有wall隔开，问在给出的图中最多能放置多少个blockhous。

思路：开始想着构建二分图匹配，但其实没那么复杂直接深搜即可

AC代码：

#include 
using namespace std;
int n, ans;
char g[15][15];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	while (cin >> n, n){
		for (int i = 0; i < n; i++)
			cin >> g[i];
		ans = 0;
		function<int(int, int)> check = [&](int a, int b){
			if (g[a][b] != '.') return 0;
			for (int i = a - 1; i >= 0; i--)
				if (g[i][b] == '?') return 0;
				else if (g[i][b] == 'X') break;
			for (int i = b - 1; i >= 0; i--)
				if (g[a][i] == '?') return 0;
				else if (g[a][i] == 'X') break;
			return 1;
		};
		function<void(int, int)> dfs = [&](int j, int cnt){
			if (j == n * n){
				ans = max(ans, cnt);
				return;
			}
			int x = j / n, y = j % n;
			if (check(x, y)){
				g[x][y] = '?';
				dfs(j + 1, cnt + 1);
				g[x][y] = '.';
			}
			dfs(j + 1, cnt);
			return;
		};
		dfs(0, 0);
		cout << ans << "\n";
	}
	return 0;
}

 Nightmare HDU - 1072

Ignatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him. The labyrinth has an exit, Ignatius should get out of the labyrinth before the bomb explodes. The initial exploding time of the bomb is set to 6 minutes. To prevent the bomb from exploding by shake, Ignatius had to move slowly, that is to move from one area to the nearest area(that is, if Ignatius stands on (x,y) now, he could only on (x+1,y), (x-1,y), (x,y+1), or (x,y-1) in the next minute) takes him 1 minute. Some area in the labyrinth contains a Bomb-Reset-Equipment. They could reset the exploding time to 6 minutes.

Given the layout of the labyrinth and Ignatius' start position, please tell Ignatius whether he could get out of the labyrinth, if he could, output the minimum time that he has to use to find the exit of the labyrinth, else output -1.

Here are some rules:
1. We can assume the labyrinth is a 2 array.
2. Each minute, Ignatius could only get to one of the nearest area, and he should not walk out of the border, of course he could not walk on a wall, too.
3. If Ignatius get to the exit when the exploding time turns to 0, he can't get out of the labyrinth.
4. If Ignatius get to the area which contains Bomb-Rest-Equipment when the exploding time turns to 0, he can't use the equipment to reset the bomb.
5. A Bomb-Reset-Equipment can be used as many times as you wish, if it is needed, Ignatius can get to any areas in the labyrinth as many times as you wish.
6. The time to reset the exploding time can be ignore, in other words, if Ignatius get to an area which contain Bomb-Rest-Equipment, and the exploding time is larger than 0, the exploding time would be reset to 6.

Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case starts with two integers N and M(1<=N,Mm=8) which indicate the size of the labyrinth. Then N lines follow, each line contains M integers. The array indicates the layout of the labyrinth.
There are five integers which indicate the different type of area in the labyrinth:
0: The area is a wall, Ignatius should not walk on it.
1: The area contains nothing, Ignatius can walk on it.
2: Ignatius' start position, Ignatius starts his escape from this position.
3: The exit of the labyrinth, Ignatius' target position.
4: The area contains a Bomb-Reset-Equipment, Ignatius can delay the exploding time by walking to these areas.

Output

For each test case, if Ignatius can get out of the labyrinth, you should output the minimum time he needs, else you should just output -1.

Sample

3 
3 3 
2 1 1 
1 1 0 
1 1 3 
4 8 
2 1 1 0 1 1 1 0 
1 0 4 1 1 0 4 1 
1 0 0 0 0 0 0 1 
1 1 1 4 1 1 1 3 
5 8 
1 2 1 1 1 1 1 4 
1 0 0 0 1 0 0 1 
1 4 1 0 1 1 0 1 
1 0 0 0 0 3 0 1 
1 1 4 1 1 1 1 1 

4 
-1 
13

原题链接:传送门

题意：每个炸弹是6分钟，2是起点3是终点，1什么都没有，0是墙不能走，4能延迟爆炸

思路：bfs中模拟这5种状态

#include 
using namespace std;
const int N = 8;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
struct node{
  int x, y, step, ti;
}t, tt;
int n, m, sx, sy, ex, ey;
int g[N][N];
int f[N][N];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int test;
  cin >> test;
  while(test--){
    for(int i = 0; i <= N; i++)
      for(int j = 0; j <= N; j++)
        f[i][j] = 6;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++){
        cin >> g[i][j];
        if(g[i][j] == 2) sx = i, sy = j;
        if(g[i][j] == 3) ex = i, ey = j; 
      }
    int ans = -1;
    function<int(int, int)> bfs = [&] (int x, int y){
      queue q;
      q.push({x, y, 0, 0});
      while(!q.empty()){
        t = q.front(), q.pop();
        if(t.x == ex && t.y == ey) {
          ans = t.step;
          return 1;
        }
        for(int i = 0; i < 4; i++){
          tt.x = t.x + dx[i], tt.y = t.y + dy[i];
          if(tt.x < 0 || tt.x >= n || tt.y < 0 || tt.y >= m || g[tt.x][tt.y] == 0) continue;
          int k = g[tt.x][tt.y];
          if(k == 1 || k == 3 || k == 4) tt.step = t.step + 1, tt.ti = t.ti + 1;
          if(tt.ti == 6) continue;
          if(k == 4) tt.ti = 0;
          if(tt.ti < f[tt.x][tt.y]) f[tt.x][tt.y] = tt.ti, q.push(tt);
        }
      }
      return 0;
    };
    int flag = bfs(sx, sy);
    if(!flag) cout << "-1\n";
    else cout << ans << "\n";
  }
}

Rescue HDU - 1242

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

Input

First line contains two integers stand for N and M.

Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.

Process to the end of the file.

Output

For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."

Sample

7 8 
#.#####. 
#.a#..r. 
#..#x... 
..#..#.# 
#...##.. 
.#...... 
........ 

13 

原题链接:传送门

题意：r->a的最短时间，遇到x时间多加1

#include 
using namespace std;
const int N = 205;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
struct node{
  int x, y, step;
}t, tt;
int n, m, sx, sy, ex, ey;
char g[N][N];
bool vis[N][N];
int f[N][N];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  while(cin >> n >> m){
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++){
        cin >> g[i][j];
        if(g[i][j] == 'r') sx = i, sy = j;
        if(g[i][j] == 'a') ex = i, ey = j; 
      }
    memset(f, 0x1f, sizeof f);
    function<void(int, int)> bfs = [&] (int x, int y){
      queue q;
      q.push({x, y, 0});
      vis[x][y] = 1;
      while(!q.empty()){
        t = q.front(), q.pop();
        for(int i = 0; i < 4; i++){
          tt = {t.x + dx[i], t.y + dy[i], t.step + 1};
          if(tt.x < 0 || tt.x >= n || tt.y < 0 || tt.y >= m || g[tt.x][tt.y] == '#') continue;
          if(g[tt.x][tt.y] == 'x') tt.step ++;
          if(tt.step < f[tt.x][tt.y]) f[tt.x][tt.y] = tt.step, q.push(tt);
        }
      }
    };
    bfs(sx, sy);
    int ans = f[ex][ey];
    if(ans == 0x1f1f1f1f) cout << "Poor ANGEL has to stay in the prison all his life.\n";
    else cout << ans << "\n";
  }
}