洛谷 P3956 棋盘（记忆化搜索）

嗯...

题目链接：https://www.luogu.org/problem/P3956

这是一道比较好搜的题，注意一些剪枝、预处理和魔法的处理问题（回溯）。

AC代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 
 5 using namespace std;
 6 
 7 int n, m, ans = 0x7ffffff;
 8 int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
 9 int mp[110][110], dp[110][110];
10 
11 inline void dfs(int x, int y, int sum, bool magic){
12     if(x < 1 || y < 1 || x > m || y > m) return;
13     if(sum >= dp[x][y]) return;//记忆化剪枝 
14     dp[x][y] = sum;
15     if(x == m && y == m) {ans = min(ans, sum); return;}
16     for(int i = 0; i < 4; i++){
17         int nx = x + dir[i][0];
18         int ny = y + dir[i][1];
19         if(nx < 1 || ny < 1 || nx > m || ny > m) continue;
20         if(mp[nx][ny]){
21             if(mp[x][y] == mp[nx][ny]) dfs(nx, ny, sum, 0);
22             else dfs(nx, ny, sum+1, 0);
23         }
24         else{
25             if(!magic){
26                 mp[nx][ny] = mp[x][y];
27                 dfs(nx, ny, sum+2, 1);
28                 mp[nx][ny] = 0;
29             }//处理魔法，注意回溯 
30         }
31     }
32 }
33 
34 int main(){
35     memset(dp, 0x3f3f3f, sizeof(dp));
36     scanf("%d%d", &m, &n);
37     for(int i = 1; i <= n; i++){
38         int x, y, c;
39         scanf("%d%d%d", &x, &y, &c);
40         mp[x][y] = c + 1;
41         //无色-0 
42     }
43     dfs(1, 1, 0, 0);
44     printf("%d", ans == 0x7ffffff ? -1 : ans);
45     return 0;
46 }

AC代码