首页 > 阿里4.10号笔试第二题
头像
小焕哒哒哒
编辑于 2020-04-10 11:13
+ 关注

阿里4.10号笔试第二题

求各位大神看看这个dfs怎么通过0.。。。

#include
using namespace std;
int n, m, c, t;
int vis[50][50];
vectorv;
int dir[4][2] = { 0,1,1,0,0,-1,-1,0 };
int dfs(int x, int y)
{
 if (x == n + 1)
 {
  /*for (int i = 1; i <= n; i++)
   for (int j = 1; j <= m; j++)
    cout << vis[i][j] << (j == m ? '\n' : ' ');*/
  return 1;
 }
 for (int i = 1; i <= c; i++)
 {
  if (v[i])
  {
   int flag = 0;
   for (int j = 0; j < 4; j++)
   {
    int xx = x + dir[j][0];
    int yy = y + dir[j][1];
    if (vis[xx][yy] == i)
    {
     flag = 1;
     break;
    }
   }
   if (flag)continue;
   vis[x][y] = i;
   v[i]--;
   int new_x = x;
   int new_y = y+1;
   if (new_y == m+1) new_x++, new_y = 1;
   int ans = dfs(new_x, new_y);
   vis[x][y] = 0;
   v[i]++;

   if (ans) return 1;
  }
 }
 return 0;
}
int main()
{
 //ifstream cin("input.txt");
 cin >> t;
 while (t--)
 {
  cin >> n >> m>> c;
  v.clear();
  memset(vis, 0, sizeof vis);
  v.push_back(0);
  for (int i = 1; i <= c; i++)
  {
   int tem;
   cin >> tem;
   v.push_back(tem);
  }
  cout << (dfs(1, 1) ? "YES" : "NO") << endl;
 }
}

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐