練習問題7-15最大数UVa 11882
1.タイトル説明:クリックしてリンクを開く
2.解題の考え方:本題は「DFS+枝切り」で解決する.この問題では、マトリクスに数値チェーンを見つけて、できるだけ大きくする必要があります.単純にdfsで盲目的な検索を行うだけでは,時間の複雑さはNであることは想像に難くない.レベルでは、ここでNはマトリクス内のすべての数値の個数を表す.時間の出費が大きすぎて、耐えられない.最適化が必要です.
では、本題はどのように最適化すればいいのでしょうか.観察により,本題は2つの最適化が可能であり,見つかった答え配列がbであり,現在試みられている配列がcであり,現在記入する位置がcurであると仮定した.答えの長さはmaxdで、b,cの2つの数のグループがcurの前のすべての数字が等しいが、現在記入する値valまた,maxdと現在位置curにより,さらに探すべき数字の個数がresであることが分かる.現在入力されている値valに対応する座標が(x,y)である場合、find(x,y)関数を使用して、後で最も多く見つけられる数を表します.find(x,y)これにより,このような2回の剪定により,時間的複雑さの大きな最適化が可能となる.行列に障害格がなく、すべての数字が同じ場合に限って最悪の場合、複雑度はO(N!)であり、しかし、多くの場合、複雑さはこの値よりはるかに小さい.
本題の学習に値する点は以下の点である:(1)適切な枝切りを習得し、「予測」があるノードからより優れた解を見つけることができるかどうか.(2)行列の中の数字が使われたかどうかは,配列タグのほかに,0のような特殊な数字に直接設定し,最後に復元すればよい.しかし、入力した数字には絶対に0が含まれていないことを保証します.
3.コード:
2.解題の考え方:本題は「DFS+枝切り」で解決する.この問題では、マトリクスに数値チェーンを見つけて、できるだけ大きくする必要があります.単純にdfsで盲目的な検索を行うだけでは,時間の複雑さはNであることは想像に難くない.レベルでは、ここでNはマトリクス内のすべての数値の個数を表す.時間の出費が大きすぎて、耐えられない.最適化が必要です.
では、本題はどのように最適化すればいいのでしょうか.観察により,本題は2つの最適化が可能であり,見つかった答え配列がbであり,現在試みられている配列がcであり,現在記入する位置がcurであると仮定した.答えの長さはmaxdで、b,cの2つの数のグループがcurの前のすべての数字が等しいが、現在記入する値val
本題の学習に値する点は以下の点である:(1)適切な枝切りを習得し、「予測」があるノードからより優れた解を見つけることができるかどうか.(2)行列の中の数字が使われたかどうかは,配列タグのほかに,0のような特殊な数字に直接設定し,最後に復元すればよい.しかし、入力した数字には絶対に0が含まれていないことを保証します.
3.コード:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;
struct Node
{
int val, x, y;
bool operator<(const Node&r)const
{
return val>r.val;
}
};
int cnt;
int n, m, maxd;//maxd
#define N 35
#define For(i,n) for(int i=0;i<(n);i++)
int b[N], c[N];//b ，c
int vis[N][N];
int a[N][N];// ，'#' 0
const int dx[] = { 0, 0, -1, 1 };
const int dy[] = { -1, 1, 0, 0 };
int find(int x, int y)// (x,y)
{
int ret = 0;
vis[x][y] = cnt;
For(k, 4){
int i = x + dx[k], j = y + dy[k];
if (!a[i][j] || vis[i][j] == cnt)continue;
ret += find(i, j) + 1;//
}
return ret;
}
bool dfs(int cur, int val, int x, int y, bool same)// cur, val, (x,y)，same cur ,
{
if (same&&val < b[cur])return 0;// cur cur < ， （1）
if (val>b[cur])same = 0;// ，
c[cur] = val;
if (cur == maxd){
for (int i = 1; i <= maxd; i++)
b[i] = c[i];
return 1;// ， 1，
}
int res = maxd - cur; cnt++;//res ，cnt ，
if (find(x, y) < res)return 0;// < ， （2）
vector<Node>L;
For(k, 4){
int i = x + dx[k], j = y + dy[k];
if (!a[i][j])continue;
L.push_back(Node{ a[i][j], i, j });// L
}
sort(L.begin(), L.end());// ，
bool o = 0;
For(i, L.size()){
int&t = a[L[i].x][L[i].y];
int tmp = t; t = 0;
o |= dfs(cur + 1, L[i].val, L[i].x, L[i].y, same);
if (o)same = 1;
t = tmp;
}
return o;
}
char st[100];
void solve()
{
vector<Node>L;
memset(a, 0, sizeof(a));
memset(vis, 0, sizeof(vis));
memset(b, 0, sizeof(b)); cnt = 0;
maxd = 0;
for (int i = 1; i <= n; i++)
{
scanf("%s", st + 1);
for (int j = 1; j <= m; j++)
{
if (st[j] != '#'){
a[i][j] = st[j] - '0';
L.push_back(Node{ a[i][j], i, j });
maxd++;
}
}
}
sort(L.begin(), L.end());//
for (; maxd >= 1; maxd--)// ， ， ， ，
{
bool o = 0;
for (int i = 0; i < L.size(); i++){
int&t = a[L[i].x][L[i].y];
int tmp = t; t = 0;// (x,y) ，
o |= dfs(1, L[i].val, L[i].x, L[i].y, 1);// same 1
t = tmp;//
}
if (o)break;// ， break
}
for (int i = 1; i <= maxd; i++)
printf("%d", b[i]);
puts("");
}
int main()
{
freopen("t.txt", "r", stdin);
while (~scanf("%d%d", &n, &m) && (n || m))
solve();
return 0;
}